Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Arrangement_with_history_2 insert and remove complexity

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Arrangement_with_history_2 insert and remove complexity


Chronological Thread 
  • From: Efi Fogel <>
  • To:
  • Subject: Re: [cgal-discuss] Arrangement_with_history_2 insert and remove complexity
  • Date: Thu, 7 Feb 2013 22:00:56 +0200

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    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/





Archive powered by MHonArc 2.6.18.

Top of Page