An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments

摘要: This paper presents an almost optimal algorithm that computes the Voronoi diagram of a set S n line segments may intersect or cross each other. If there are k intersections among input in S, our takes O ( α ) log ? + time, where denotes inverse Ackermann function. The best known running time prior to this work was . Since lower bound problem is shown be worst case, worst-case for = , and only factor away from any optimal-time algorithm, which still unknown. For purpose, we also present improved medial axis polygon with holes.