CGAL users discussion list

[Efi Fogel <>]

The asymptotic complexity of the implemented alg. is O(n log n) for applying n insertions and removals, which is the tight bound of the theoretical asymptotic complexity. I think, though, that what's more important is the hidden constant. You will have to play with it a bit and gain experience to get a feeling for the actual complexity. Notice also that the presence of many holes may have an effect on the time consumption.

On Thu, Feb 7, 2013 at 7:36 AM, Victor Lopez <> wrote:

Hello,

What is the time complexity of following functions:

remove(arr,ch)
insert(arr,c)

used to remove and insert a curve into a Arrangement_with_history_2?

I'm using CGAL arrangements as the dual space of a set of points and I would like to know how much it will cost to move a point/update the arrangement.

Thanks.

Victor

--

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