REPRESENTING THE VORONOI DIAGRAM OF A SIMPLE POLYGON USING RATIONAL QUADRATIC BEZIER CURVES

The Voronoi diagram of a set of geometric entities on a plane, such as points, line segments, or arcs, is a collection of Voronoi polygons a ssociated with each entity, where the Voronoi polygon of an entity is a set of points which are closer to the associated entity than any oth er entity. A Voronoi diagram is one of the most fundamental geometrica l constructs, and it is well known for its theoretical elegance and th e wealth of applications. Various geometric problems can be solved wit h the aid of Voronoi diagrams. The paper discusses an algorithm to con struct the Voronoi diagram of the interior of a simple polygon which c onsists of simple curves such as line segments as well as arcs in a pl ane with O(N log N) time complexity by the use of a divide-and-conquer scheme. Particular emphasis is placed on the parameterization of bise ctors using a rational quadratic Bezier curve representation which uni fies four different bisector cases.