Skip to Content.
Sympa Menu

cgal-discuss - Voronoi diagram -- some theoretical questions

Subject: CGAL users discussion list

List archive

Voronoi diagram -- some theoretical questions


Chronological Thread 
  • From: Banerjee <>
  • To:
  • Cc: Bonny Banerjee <>
  • Subject: Voronoi diagram -- some theoretical questions
  • Date: Sun, 14 Jan 2007 10:37:41 -0800 (PST)
  • Domainkey-signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:X-YMail-OSG:Received:Date:From:Subject:To:Cc:MIME-Version:Content-Type:Content-Transfer-Encoding; b=uAh3OUFaCvV8uwRtX9WTOKGg9HrRDx/MEBhEv/CHR5jmmPu/fce1XpcXU9DzNVDXjXX7Rg/I0QuFdXO39cwAML2P/j8nj8oLqRT0T2HiL0/7Qm0BF6GCVbPcVfRLje1LgJfO+2pzdT582LkUOQhM+7aF8/CzOldWc6VSeIpGRio= ;

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



  • Voronoi diagram -- some theoretical questions, Banerjee, 01/14/2007

Archive powered by MHonArc 2.6.16.

Top of Page