Other Scholarly Content


On the design of flipping algorithm for Voronoi diagram of polygons Public Deposited

Downloadable Content

Download PDF


Attribute NameValues
  • Abstract: In this project, our goal is to design a flipping algorithm for computing the Voronoi diagram of simple polygons. As preparation towards designing a flipping algorithm, we re­-implemented the ear cutting algorithm of using a standard geometric library COAL. This new Implementation is compatible with COAL, We have designed a flipping algorithm using a reasonable definition of "triangulation" of a set of point and segment sites. However, our algorithm is not provably correct and may sometimes fail to compute the Voronoi diagram. Before this project, it was conjectured and believed that such an algorithm. will correctly compute the Voronoi diagram. Our implementation bas revealed the difficulties in generalizing the flipping algorithm. The software we have developed can be easily modified to test future attempts towards generalizing the flipping algorithm. While working on this project, we have obtained an alternative proof of termination for the flipping algorithm for points. This proof can potentially be generalized for segments.
  • 2001 best estimate for issue date based on available information.
Resource Type
Date Issued
Academic Affiliation
Rights Statement
Peer Reviewed



This work has no parents.