Title: Hamiltonian abstract Voronoi diagrams in linear time
Abstract: Let V(S) be an abstract Voronoi diagram, and let H be an unbounded simple curve that visits each of its regions exactly once. Suppose that each bisector B(p, q), where p and q are in S, intersects H only once. We show that such a "Hamiltonian" diagram V(S) can be constructed in linear time, given the order of Voronoi regions of V(S) along H. This result generalizes the linear time algorithm for the Voronoi diagram of the vertices of a convex polygon. We also provide, for any δ > log60/29 2, an O(n δ)-time parallelization of the construction of the V(S) optimal in the time-processor product sense.
Publication Year: 1994
Publication Date: 1994-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 19
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot