Subject: CGAL users discussion list
List archive
- 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 /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
/_____/_) o /__________ __ //
(____ ( ( ( (_/ (_/-(-'_(/
_/
- [cgal-discuss] Arrangement_with_history_2 insert and remove complexity, Victor Lopez, 02/07/2013
- Re: [cgal-discuss] Arrangement_with_history_2 insert and remove complexity, Efi Fogel, 02/07/2013
Archive powered by MHonArc 2.6.18.