DocumentCode
2829257
Title
On 2-Site Voronoi Diagrams under Geometric Distance Functions
Author
Barequet, Gill ; Dickerson, Matthew T. ; Eppstein, David ; Hodorkovsky, David ; Vyatkina, Kira
Author_Institution
Dept. of Comput. Sci., Technion - Israel Inst. of Technol., Haifa, Israel
fYear
2011
fDate
28-30 June 2011
Firstpage
31
Lastpage
38
Abstract
We revisit a new type of a Voronoi diagram, in which distance is measured from a point to a pair of points. We consider a few more such distance functions, based on geometric primitives, and analyze the structure and complexity of the nearest- and furthest-neighbor Voronoi diagrams of a point set with respect to these distance functions.
Keywords
computational geometry; 2-site Voronoi diagrams; furthest-neighbor Voronoi diagrams; geometric distance functions; nearest-neighbor Voronoi diagrams; Complexity theory; Computer science; Context; Electronic mail; Joining processes; Machinery; Davenport-Schinzel theory; crossing-number lemma; distance function; lower envelope;
fLanguage
English
Publisher
ieee
Conference_Titel
Voronoi Diagrams in Science and Engineering (ISVD), 2011 Eighth International Symposium on
Conference_Location
Qingdao
Print_ISBN
978-1-4577-1026-1
Electronic_ISBN
978-0-7695-4483-0
Type
conf
DOI
10.1109/ISVD.2011.13
Filename
5988944
Link To Document