Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments
(Extended Abstract)
verfasst von : Sang Won Bae
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper presents an almost optimal algorithm that computes the Voronoi diagram of a set
S
of
n
line segments that may intersect or cross each other. If there are
k
intersections among the input segments in
S
, our algorithm takes
O
(
n
α
(
n
) log
n
+
k
) time, where
α
(·) denotes the functional inverse of the Ackermann function. The best known running time prior to this work was
O
((
n
+
k
) log
n
). Since the lower bound of the problem is shown to be Ω(
n
log
n
+
k
) in the worst case, our algorithm is worst-case optimal for
k
= Ω(
n
α
(
n
) log
n
), and is only a factor of
α
(
n
) away from the lower bound. For the purpose, we also present an improved algorithm that computes the medial axis or the Voronoi diagram of a polygon with holes.