2015 | OriginalPaper | Buchkapitel
An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments
(Extended Abstract)
Autor: Sang Won Bae
Verlag: Springer International Publishing
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.
