Фортунов алгоритам

Фортунов алгоритам је алгоритам покретне линије ѕа генерисање Воронојевих дијаграма из скупа тачака у равни чија је временска сложеност O(n log n) и просторна O(n).[1][2] Објавио га је Стивен Фортун 1986. у свом раду "Алгоритам покретне линије за Воронојеве дијаграме."[3]

Fortune's algorithm animation

Опис алгоритма

уреди

Алгоритам одржава покретну линију и обалску линију, које се обе крећу кроз раван како алгоритам напредује. Покретна линија је права линија, и можемо по договору претпоставити да је вертикална и да се креће слева надесно. У било ком тренутку током трајања алгоритма тачке лево од покретне линије ће бити уграђене у Воронојев дијаграм, док тачке десно од покретне линије нису још увек разматране. Обалска линија није линија, већ комплексна крива са леве стране покретне која се састоји од делова парабола; она раздваја део равни у којем Воронојев дијаграм може бити познат, без обзира на тачке десно од покретне линије, од остатка равни. За сваку тачку лево од покретне линије, може се дефинисати парабола тачака које су на подједнаком растојању од те тачке и од покретне линије; обалска линија је граница уније ових парабола. Док покретна линија напредује, темена обалске линије, у којој се две параболе секу, прати ивице Воронојевог дијаграма. Обалска линија напредује чувајући сваку параболу тачно на пола пута између тачака преко којих се претходно прешло покретном линијом и новог положаја покретне линије.

Алгоритам одржава као структуру података бинарно стабло претраге које описује структуру обалске линије и приоритетни ред који садржи потенцијалне будуће догађаје који могу да промене структуру обалске линије. Ови догађаји укључују додавање нове параболе у обалску линију (када покретна линија наиђе на нову улазну тачку) и уклањање криве из обалске линије (када покретна линија постане тангента на кругу кроз неке три улазне тачке чије параболе формирају узастопне сегменте обалске линије). Приоритет сваког таквог догађаја се може одредити на основу x-координате покретне линије у тачки у којој се догађај десио. Сам алгоритам се онда састоји од уклањања следећег догађаја из приоритетног реда, проналажења промена које догађај проузрокује у обалској линији и ажурирања структура података.

Пошто има O(n) догађаја које треба обрадити (сваки је повезан са неком карактеристиком Воронојевог дијаграма) и O(log n) времена за обраду догађаја (сваки се састоји од константног броја операција на бинарном стаблу претраге и приоритетном реду) укупно време је O(n log n).

Псеудокод

уреди

Псеудокод опис алгоритма.[4]

let   be the transformation  ,
  where   is the Euclidean distance between   and the nearest site
let   be the "beach line"
let   be the region covered by site  .
let   be the boundary ray between sites   and  .
let   be the sites with minimal  -coordinate, ordered by  -coordinate
 
create initial vertical boundary rays  
 
while not IsEmpty( ) do
      ← DeleteMin( )
    case   of
      is a site in  :
        find the occurrence of a region   in   containing  ,
          bracketed by   on the left and   on the right
        create new boundary rays   and   with bases  
        replace   with   in  
        delete from   any intersection between   and  
        insert into   any intersection between   and  
        insert into   any intersection between   and  
      is a Voronoi vertex in  :
        let   be the intersection of   on the left and   on the right
        let   be the left neighbor of   and
          let   be the right neighbor of   in  
        create a new boundary ray   if  ,
          or create   if   is right of the higher of   and  ,
          otherwise create  
        replace   with newly created   in  
        delete from   any intersection between   and  
        delete from   any intersection between   and  
        insert into   any intersection between   and  
        insert into   any intersection between   and  
        record   as the summit of   and   and the base of  
        output the boundary segments   and  
    endcase
endwhile
output the remaining boundary rays in  

Тежинске локације и дискови

уреди

Као што Фортун описује у[1] модификована верзија алгоритма покретне линије може бити искоришћена за конструкцију адитивног тежинског Воронојевог дијаграма, у коме удаљеност до сваке локације (генератора) је померена за тежину локације; ово може бити еквивалентно посматрано као Воронојев дијаграм скупа дискова чији је центар у локацијама са радијусом једнаким тежини локације.

Референце

уреди
  1. ^ а б Mark de Berg; Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised изд.), Springer-Verlag, ISBN 978-3-540-65620-3  Section 7.2: Computing the Voronoi Diagram: pp. 151—160.
  2. ^ Austin, David, Voronoi Diagrams and a Day at the Beach, Feature Column, American Mathematical Society 
  3. ^ Steven Fortune. A sweepline algorithm for Voronoi diagrams. Proceedings of the second annual symposium on Computational geometry. Yorktown Heights, New York, United States. . 1986. стр. 313—322. ISBN 978-0-89791-194-8.  Недостаје или је празан параметар |title= (помоћ) ACM Digital LibrarySpringerLink[мртва веза]
  4. ^ Wong, Kenny; Hausi A. Müller, An Efficient Implementation of Fortune's Plane-Sweep Algorithm for Voronoi Diagrams, CiteSeerX 10.1.1.83.5571  

Спољашње везе

уреди