CGAL users discussion list

[Mael <>]

Hello,

Although the main code indeed uses Bowyer-Watson, there is some code 
about flipping in the packages Triangulation_3 and TDS_3. However, these 
are mostly atomatic operations at the base triangulation level, and 
there are no complete function doing an insertion in a (weighted) 
Delaunay triangulation like there are in the package Triangulation_2.

Best,
Mael

On 14/01/2020 10:05, Marc Alexa wrote:
> Thanks a lot for the answers.
>
> My understanding from the lifting picture is that the point first “appears” when 
> it is connected to the vertices of the cell that contains it (assuming it is 
> inserted inside the convex hull of the points). Then the motion in the lift 
> downwards corresponds to the sequence of flips one would perform in the 
> incremental flipping approaches (Edelsbrunner & Shah, Incremental topological 
> flipping works for regular triangulations). This is nicely explained in the 
> Triangulations book by De Loera, Rambau and Santos, Section 5.3.2. on Monotone 
> paths in the secondary polytope.
>
> So in terms of implementation it would probably suffice if the incremental 
> flipping approach was implemented somewhere in CGAL. But I guess CGAL only 
> uses Bowyer-Watson? Or is there some code somewhere for incremental flipping?
>
> Thanks!-Marc
>
>
>
>
>
> > On 9. Jan 2020, at 09:34, Mael 
> > <>
> >  wrote:
> >
> > Hello
> >
> > Here is a translation of an answer by Jean-Daniel Boissonnat in private 
> > correspondence:
> >
> > > Considering the usual lifting into R^{d+1} (R^4 here), let p1, ..., pn be 
> > > points in R^3 and P1, ..., Pn their lifted equivalent, i.e. Pi = (pi, pi^2).
> > > Let x be the new point, X=(x, x^2), and T the face of the convex hull 
> > > conv(P1, ..., Pn) whose projection onto R^3 contains x.
> > > The 4th coordinate of the lifted point X (and thus its weight) must be chosen 
> > > such that X is below conv(P1, ..., Pn). To ensure that no point disappears, 
> > > the new convex hull conv(P1, ..., Pn, X) must have all points as vertices,
> > > in other words X must be above the planes of the faces of convex(P1, ..., Pn) 
> > > that are adjacent to T.
> > > This can be expressed with circumscribing balls in R^3.
> > As to get the triangulations that appear when moving within this range, you 
> > can probably use a similar reasoning as the combinatorics will change when an 
> > adjacent face is no longer on the convex hull.
> >
> > There also used to be a package called Kinetic Data Structure in CGAL, it 
> > could handle Regular_triangulation_3 but I am not sure if the kinetic change 
> > had to be the position of a point with a fixed weight, or if you could also 
> > change weights.
> >
> > Best,
> > Mael
> >
> > On 07/01/2020 19:18, Marc Alexa wrote:
> > > Dear all,
> > >
> > > I want to insert a point p into a regular triangulation. The point has a 
> > > fixed coordinate. I am interested in the interval of weights so that the 
> > > point itself appears in the triangulation and none of the existing points 
> > > disappears. The upper bound (the point appears) is easy: find the cell the 
> > > contains p. The cell defines a hyperplane in the lift, and the lift for p 
> > > needs to be below the hyperplane. What methods are available in CGAL that 
> > > would help me finding the lower bound? Moreover, is there an easy way to walk 
> > > through all triangulations in this interval, perhaps parameterized by the 
> > > weight?
> > >
> > > Thanks!
> > > -Marc
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://sympa.inria.fr/sympa/info/cgal-discuss