# Inserting a point into a regular triangulation so that it appears and no other vertex disappears

5 messages
Open this post in threaded view
|

## Inserting a point into a regular triangulation so that it appears and no other vertex disappears

 CONTENTS DELETED The author has deleted this message.
Open this post in threaded view
|

## Re: Inserting a point into a regular triangulation so that it appears and no other vertex disappears

 CONTENTS DELETED The author has deleted this message.
Open this post in threaded view
|

## Re: Inserting a point into a regular triangulation so that it appears and no other vertex disappears

 In reply to this post by Marc Alexa 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