CGAL users discussion list

[Marc Alexa <>]

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
> 
>