# 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

 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
Open this post in threaded view
|

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

 Dear Marc, I think such a weight does not always exist. Implementation wise, I would do the following: a) locate the cell containing the point to be inserted b) Use the power test (Power_side_of_oriented_power_sphere_3) with the 4 points of the cell to check if the new point is hidden c) if it is, go back to the definition of the power test and get the minimal weight so that the point is orthogonal to the power sphere of the cell (note that you'll have to resort to exact arithmetic if you want an exact value and then take approx(w).sup() if you want to go back to the floating point world) d) together with your minimal weight, call find_conflict(). If there is a vertex that is surrounded by cells in conflict then the new point will hide a previously inserted point. If not, you can get the upper bound by considering the cells incident to the current region in conflict (but not in that region) and use the definition of the power test to get for each such cell the maximum value of the weight until the point is orthogonal to the power sphere of that cell. You of course have to handle the case when the dimension is not 3 and when the point fall outside the convex hull (which simply mean that the minimal weight is 0). HTH, Sebastien. On 1/7/20 7:18 PM, 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
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