On the design of flipping algorithm for Voronoi diagram of polygons

Público Deposited

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

Descriptions

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
Fecha de Emisión	2001
Academic Affiliation	Computer Science
Declaración de derechos	In Copyright
Publisher	Oregon State University. Department of Computer Science
Peer Reviewed	No
Language	English [eng]

Miniatura	Título	Fecha de subida	Visibilidad	Acciones
	Wu_Yi_Flipping_Algorithm.pdf	2023-03-29	Público	Descargar