On the design of flipping algorithm for Voronoi diagram of polygons

Other Scholarly Content

Analytics

Citeable URL: https://ir.library.oregonstate.edu/concern/defaults/3197xv75z

Attribute Name	Values
Creator	Wu, Yi
Abstract	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	Research Paper
Date Issued	2001
Academic Affiliation	Computer Science
Rights Statement	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]

Thumbnail	Title	Date Uploaded	Visibility	Actions
	Wu_Yi_Flipping_Algorithm.pdf	2023-03-29	Public	Download