Subject: CGAL users discussion list
List archive
- 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.
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.