CGAL users discussion list

[Banerjee <>]

I have a few theoretical questions regarding Voronoi diagram.

 

1. I am computing the Voronoi diagram of a set of n polygonal regions in 2D, where one region contains all the other n-1 regions. See attached file CleanMedialAxis.eps for a Voronoi diagram of a dataset of n=14 regions. The time complexity for computing the Voronoi diagram is O(NlogN + nN), where N is the number of vertices (sampled points) on the n polygons [Srinivasan & Nackman, 1987]. Please let me know if you are aware of a better complexity result.

2. In the domain I am working, some of the regions might be deleted or some new regions might be introduced or shape and/or location of some of the regions might be altered. In such cases, I do not want to re-compute the entire Voronoi diagram from scratch. Rather, I would like to update the existing Voronoi diagram, to obtain the Voronoi diagram for the modified scenario, assuming that would incur lesser computational cost.         

            I am aware of the result that insertion and deletion of a point P can be performed in O(logN) expected time, assuming P is chosen from the set of generators with equal probability. Also, insertion and deletion of a line segment can be performed in O(logN) time [Gold, Remmele and Roos, 1999]. What is the complexity of insertion/deletion of polygonal regions in a Voronoi diagram of regions?

 

3. I also need an upper bound on the number of simple paths from a given vertex in a planar undirected graph (such as the Voronoi diagram of regions). I searched the web but could not find any relevant result. The closest I could find was upper and lower bounds on the number of simple cycles in a planar undirected graph which are O(3.37^|V|) and Omega(2.28^|V|) respectively [Alt, Fuchs & Kriegel, 1999], where |V| is the number of vertices in the graph. According to my calculations, the upper bound on the number of simple paths from a given vertex in a planar undirected graph is O(5^|V|). If you are aware of any better bound, please do let me know.

 

4. What is the upper bound on the number of simple paths between two given vertices in a planar undirected graph (such as the Voronoi diagram of regions)?

 

Thanks much,

Bonny.

 

*****************************************************************************************************

 

References:

 

V. Srinivasan and L. R. Nackman, "Voronoi diagram for multiply-connected polygonal domains I: Algorithm", IBM Journal of Research and Development, 31(3), pp. 361-372, 1987.

 

C. Gold, P. Remmele and T. Roos, "Fully dynamic and kinematic Voronoi diagrams in GIS", Algorithmica:Special Issue on Cartography and GIS, 1999.

 

H. Alt, U. Fuchs and K. Kriegel, "On the number of simple cycles in planar graphs", Combinatorics, Probability and Computing, 8(5), pp. 397-405, 1999.

---

Be a PS3 game guru.
Get your game face on with the latest PS3 news and previews at Yahoo! Games.

Attachment: CleanMedialAxis.eps
Description: 1640357514-CleanMedialAxis.eps