CGAL users discussion list

["Vu, Khuong" <>]

As I mentioned in the earlier email, Voronoi vertices may have the same set 
of constructing sites. I think this may cause the problem in the adapter. 

To make it systematic, I think we should prove:
1. It can be proved that given any Delaunay diagram of line segments and 
points which presents a face by 3 sites as implemented in CGAL , a unique 
corresponding Voronoi diagram can be constructed, in which vertices' 
coordinates are determined uniquely. 
2. More importantly, a linear-time adapting algorithm can be devised. 

I don't know if those facts have been considered in the literature, but I 
think they are important to confirm the duality of Voronoi and Delaunay in 
the case of 2D line segments and points. I hope this helps!

Thanks for your time and effort. I appreciate it.
Khuong

________________________________________
From: Menelaos Karavelas 
[]
Sent: Friday, April 23, 2010 7:55 AM
To: 

Subject: Re: [cgal-discuss] RE: Problems on segment Voronoi diagram

I will take a look at the adaptor and get back to you.

Thanks for the "problematic" example.

- m.

On 23 Apr 2010, at 13:01, Vu, Khuong wrote:

> Segment_Delaunay_graph_hierarchy_2 really reduces the running time.
> I think we have nothing to do with the Delaunay diagram. It's
> totally correct. But converting to the Voronoi diagram takes
> forever. Could you please let us know how the Voronoi adapter works?
> I, personally, think it has a serious bug. Thanks for your help.
>
> Khuong
>
> ________________________________________
> From: Menelaos Karavelas 
> []
> Sent: Friday, April 23, 2010 4:32 AM
> To: 
> 
> Subject: Re: [cgal-discuss] RE: Problems on segment Voronoi diagram
>
> I am not really sure about that. I am attaching my version of your
> code, where I made some modifications. You will notice that I have
> commented the usage of Quotient<MP_Float> and replaced it by Gmpq.
> Also I have commented the usage of Segment_Delaunay_graph_2 and
> replaced it by Segment_Delaunay_graph_hierarchy_2. Also I am
> considering two possible ways of inserting the segments: your way (the
> simple/obvious way) and inserting the first endpoint of a segment,
> then the second using the vertex_handle returned for the first, and
> then use the two vertex handles to insert the interior of the segment
> (I call this below the polyline insertion method, whereas the first
> one is called the segments' method).
>
> Here are my running times (on a PowerPC G4) in seconds with
> optimization flags turned on (Release building mode):
>
> SDG + MP_Float + polyline: 35.5918
> SDG Hierarchy + MP_Float + segments: 35.6429
>
> SDG + Gmpq + segments: 1.19534
> SDG + Gmpq + polyline: 1.17302
>
> SDG Hierarchy + Gmpq + segments: 1.14345
> SDG Hierarchy + Gmpq + polyline: 1.17157
>
> It seems to me that the showstopper is the number type. I would
> immediately switch to Gmpq, and also use the hierarchy (it will be
> much for efficient for more input segments). I you do not want to use
> the hierarchy, then use the alternative way of inserting your input
> (this is the insertPolyline function in the code).
>
> - m.
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss