

Hello,
I have one fundamental doubt. Delaunay triangulation and Voronoi Diagrams are dual to each other. From implementation point of view, which one has less complexity ? Almost all the books in Computational
Geometry describe both the algorithms but I couldn't find the comparison between two approaches. Can someone clarify ?
Chaman Singh Verma Poona, India


>
> I have one fundamental doubt. Delaunay triangulation and Voronoi
> Diagrams are dual to each other.
Delaunay and Voronoi are two point of view for the same object
> implementation point of view, which one has less complexity ?
thus the complexity is exactly the same (since it is the same stuff)

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


It all depends on what problem you are solving. For
motion planning or obstacle avoidance, I use Delaunay.
Regards
Steve
 Original Message 
Sent: Friday, October 03, 2008 5:49
AM
Subject: [cgaldiscuss] Delaunay v/s
Voronoi
Hello,
I have one fundamental doubt. Delaunay
triangulation and Voronoi Diagrams are dual to each other.
From implementation point of view, which one has less complexity ?
Almost all the books in Computational Geometry describe both the algorithms
but I couldn't find the comparison between two approaches. Can someone
clarify ?
Chaman Singh Verma Poona,
India


> thus the complexity is exactly the same (since it is the same stuff)
I think he means "difficulty" in implementing, not actual complexity. In this
case, Delaunay seems to be the choice in CGAL, and I see it easier to implement
myself. Thanks to the empty circle condition, I would had some idea about how to
introduce new points, and retriangulate; for the Voronoi, the thing seems much
more delicate. It is true that many textbooks talk about just everything but
often fail to mention ease of implementation and applicability.
Best,
Daniel

Mensaje enviado mediante una herramienta Webmail integrada en *El Rincon*:
>>>>>>>> https://rincon.uam.es <<<<<<<<

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


> thus the complexity is exactly the same (since it is the same stuff)
I think he means "difficulty" in implementing, not actual complexity. In this
case, Delaunay seems to be the choice in CGAL, and I see it easier to implement
myself. Thanks to the empty circle condition, I would had some idea about how to
introduce new points, and retriangulate; for the Voronoi, the thing seems much
more delicate. It is true that many textbooks talk about just everything but
often fail to mention ease of implementation and applicability.
Best,
Daniel

Mensaje enviado mediante una herramienta Webmail integrada en *El Rincon*:
>>>>>>>> https://rincon.uam.es <<<<<<<<

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


In reply to this post by Daniel Duque Campayo
On Friday 03 October 2008 17:21:42 [hidden email] wrote:
> > thus the complexity is exactly the same (since it is the same stuff)
>
> I think he means "difficulty" in implementing, not actual complexity. In
> this case, Delaunay seems to be the choice in CGAL, and I see it easier to
> implement myself. Thanks to the empty circle condition, I would had some
> idea about how to introduce new points, and retriangulate; for the
> Voronoi, the thing seems much more delicate. It is true that many textbooks
> talk about just everything but often fail to mention ease of implementation
> and applicability.
For the euclidean distance, and with points in general position, computing a
Voronoi diagram and computing a Delaunay triangulation is exactly the same:
same result and same algorithm. The only difference is that for Voronoi you
need to compute Voronoi vertices (which are circumcenters).

Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


In reply to this post by Daniel Duque Campayo
Hi,
I installed CGAL a few days ago about to use the 3d delaunay function.
So I followed the example and create an Delaunay Trinagulation Object:
Triangulation T;
So I inserted my Points and all works fine.
But how can I acces the points and the faces in my Object for manually
inserting them to another object?
Can someone give me an short example plz?
Greets,
Dennis

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


Dennis Endt wrote:
> Hi,
>
> I installed CGAL a few days ago about to use the 3d delaunay function.
>
> So I followed the example and create an Delaunay Trinagulation Object:
>
> Triangulation T;
>
> So I inserted my Points and all works fine.
>
> But how can I acces the points and the faces in my Object for manually
> inserting them to another object?
>
> Can someone give me an short example plz?
>
> Greets,
> Dennis
>
>
It might help to read the manual.

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


Hello, So which method is easier to implement ? Voronoi or Delaunay csv On Fri, Oct 3, 2008 at 6:36 PM, Olivier Devillers <[hidden email]> wrote:
I have one fundamental doubt. Delaunay triangulation and Voronoi Diagrams are dual to each other.
Delaunay and Voronoi are two point of view for the same object
implementation point of view, which one has less complexity ?
thus the complexity is exactly the same (since it is the same stuff)

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

Administrator

Chaman Singh Verma a écrit :
> Hello,
>
> So which method is easier to implement ? Voronoi or Delaunay
Go for Delaunay.

Sylvain Pion
INRIA SophiaAntipolis
Geometrica ProjectTeam
CGAL, http://cgal.org/
You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


In reply to this post by Laurent Rineau (GeometryFactory)
On Fri, Oct 3, 2008 at 7:01 PM, Laurent Rineau <[hidden email]> wrote:
On Friday 03 October 2008 17:21:42 [hidden email] wrote:
> > thus the complexity is exactly the same (since it is the same stuff)
>
> I think he means "difficulty" in implementing, not actual complexity. In
> this case, Delaunay seems to be the choice in CGAL, and I see it easier to
> implement myself. Thanks to the empty circle condition, I would had some
> idea about how to introduce new points, and retriangulate; for the
> Voronoi, the thing seems much more delicate. It is true that many textbooks
> talk about just everything but often fail to mention ease of implementation
> and applicability.
For the euclidean distance, and with points in general position, computing a
Voronoi diagram and computing a Delaunay triangulation is exactly the same:
same result and same algorithm. The only difference is that for Voronoi you
need to compute Voronoi vertices (which are circumcenters).

Laurent Rineau, PhD
Engineer at GeometryFactory
http://www.geometryfactory.com/
Hello, CGAL documents don't talk about Voronoi Diagrams in 3D. Does it means that they haven't been implemented or the document need upgradation ? Thanks.
csv


Hi,
I didn`t find any exact information regarding to the needed iterators. I
searched the online documentation as well as the demos and examples.
So I tried this:
for(Triangulation::Point_iterator it = T.points_begin(); it !=
T.points_end(); it++)
{
}
But what next? How could I access the Points with the coordinates and
the facets with the points?
Furthermore the Delaunay Triangulation seems to be wrong:
The number of vertices are 8. My Object are an Rectangle.
After the Delaunay Triangulation I receive 27 edges and 36 facets??? A
very high number I think....17 edges seems to be right!
Greets
Dennis

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


Hi ,
Using CGAL::Delaunay_triangulation_{2,3} is even easier than
reprogramming Delaunay or Voronoi...
Best
Monique Teillaud
Chaman Singh Verma wrote:
> Hello,
>
> So which method is easier to implement ? Voronoi or Delaunay
>
> csv
>
>
> On Fri, Oct 3, 2008 at 6:36 PM, Olivier Devillers
> < [hidden email]
> <mailto: [hidden email]>> wrote:
>
>
>
> I have one fundamental doubt. Delaunay triangulation and Voronoi
> Diagrams are dual to each other.
>
> Delaunay and Voronoi are two point of view for the same object
>
> implementation point of view, which one has less complexity ?
>
>
> thus the complexity is exactly the same (since it is the same stuff)
>
> 
> You are currently subscribed to cgaldiscuss.
> To unsubscribe or access the archives, go to
> https://listssop.inria.fr/wws/info/cgaldiscuss>
>

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss


In reply to this post by Daniel Duque Campayo
Hi,
right.
The graphs are dual, so, when you compute a Delaunay triangulation
(provided by CGAL), you also get the graph of Voronoi.
Moreover, the Delaunay triangulation provides you with dual() functions,
that give you the geometric embedding of the Voronoi diagram.
best
Monique Teillaud
Daniel Duque Campayo wrote:

You are currently subscribed to cgaldiscuss.
To unsubscribe or access the archives, go to
https://listssop.inria.fr/wws/info/cgaldiscuss

