Representing the Voronoï diagram of a simple polygon using rational quadratic Bézier curves (Q1902425)

The authors present an algorithm for the construction of the Voronoï diagram for scenes consisting of points, line segments, polygons, and arcs. The algorithm is based on a divide-and-conquer approach and requires \(O(n \log n)\) time. Voronoï diagrams are a very important concept in many applications - - robotics, computer vision, mesh generation, and geometric modeling. The construction discussed in this paper will be very useful to speed up the generation of Voronoï diagrams. The various bisecting curves defining the Voronoï diagram are represented by means of rational Bézier curves.