CGAL users discussion list

[Efi Fogel <>]

Hi Kevin,

Inserting curves into an arrangement can be done either incrementally or in an aggregate fashion.

The incremental insertion is based on the zone framework and the aggregate insertion is based on the plane-sweep framework. There are several references to these algorithmic frameworks out there.

Inserting n curves into an arrangement using the zone framework takes O(n^2) time, while inserting n curves into an arrangement using the plane-sweep framework takes O((k+n) log(n)) time, where k is the number of intersections between the n curves.

So, if the number of intersections is expected to be small, using the plane-sweep may be advantageous. In any case, the two algorithms are completely different and so are their implementations, so you need to empirically try them out before you arrive to some conclusions.

If you know some topological information about the curves you are about to insert you can take advantage of it; look for section 2.7 Modifying the Arrangement in http://doc.cgal.org/latest/Arrangement_on_surface_2/index.html#arr_secarr_class

Efi

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

On Mon, Apr 18, 2016 at 7:59 PM, KHartmann <> wrote:

Hi,

I have used both the 2D Triangulation and 2D Arrangement classes.
I have found that adding constraint edges to a Triangulation is
extremely fast regardless of how large the Triangulation grows.
But I have found, when adding edges to an Arrangement, the insertion
time gets longer and longer as the Arrangement grows.  (I am only adding
straight line segments and x_monotone arcs).

Is this to be expected?  What is the order of these two Algorithms?
It seems that adding a constraint edge to a Triangulation might be
constant time O(1).  But perhaps adding edges to an Arrangement is somewhat
more expensive O( n-squared )?

Are there any tricks that I might use to speed up insertion time into
an Arrangement?  Right now I'm adding edges one at a time in arbitrary
order.

Thanks,
Kevin




--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Data-structure-performance-differences-tp4661842.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

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