Additively Weighted Voronoi Diagram on the Oriented Projective Plane

Abstract: We consider Voronoi diagrams defined on the oriented projective plane. In this geometry, the closest and furthest site diagrams are antipodal. We give a simple on-line incremental algorithm for constructing the additively weighted diagram. This diagram, which may be disconnected in Euclidean plane, is always connected in the oriented projective plane and has exactly $3n-6$ edges and $2n-4$ vertices, where $n$ is the number of sites.



Resumo: Nós consideramos diagramas de Voronoi definidos no plano projetivo orientado. Nesta geometria, os diagramas de vizinho mais próximo e vizinho mais distante são antipodais. Nós apresentamos um algoritmo incremental ``on-line'' para a construção do diagrama de pontos com peso aditivo. Este diagrama, que pode ser desconexo no plano Euclidiano, é sempre conexo no plano projetivo orientado e tem exatamente $3n-6$ arestas e $2n-4$ vértices, onde $n$ é o número de sítios.

2000