CGAL users discussion list

[Mael <>]

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