CGAL users discussion list

[Marc Alexa <>]

Without knowing anything about the sampling processes used to generate the points and the dimension it’s difficult to say anything — but you might just see the ‘curse of dimensionality’. Uniform random vectors in high dimension are almost always for away from each other, so they are also far away from the origin. If your domain is convex (say a sphere) and you create the points uniformly random and then reject those outside the domain, the points inside the domain are close to the boundary with very high probability. So finding many points in the cells on the boundary ("The number of points that the locate() method assigns to slivers is also totally out of proportion to the fraction of the outer shell occupied by the slivers.”) might just be the natural behavior of the sampling.

I have put together a few lines of python code to illustrate this for a sphere. Points are generated by rejection sampling from points uniformly distributed over the cube [-1,1]^D. As D grows, most points are outside of the sphere, and those inside the sphere are close to the boundary. 

Best,

Marc

import numpy as np

for D in range(1,15):

    print("Dimension: ", D)

    i = 0

    vl = np.empty(1000)

    while (i < 1000):

        cl = np.linalg.norm(2.0*np.random.rand(D)-np.full(D,1.0))

        if (cl <= 1.0):

            vl[i] = cl

            i = i + 1

    print("Norms of uniform random points in unit ball")

    print("Mean: ", np.mean(vl))

    print("Median: ", np.median(vl))

On 17. Jul 2021, at 13:51, Renaud GILLON <> wrote:

Hello,

Using the CGAL d-dimensional Delaunay_triangulation class with the Epick kernel, I want to generate triangulations in order to perform barycentric interpolation of a multi-dimensional function sampled along with its derivatives at the location of the vertices of the triangulation.

Because of the nature of the sampled function, the sampling grid is rather anisotropic (the spacing in one direction is 1.0E4 times larger than in the others) in some region. Despite this difficulty, the Delaynay mesh is nice (uniform volumes) on the inside. It just has slivers (quasi-zero volume cells) on the outside.

Initially, I was hoping to push the slivers out by adding "padding" (dummy points) on the periphery where the slivers are occurring, so that test points would always reside in a well formed cell.

However, I noticed that slivers seem to behave as "strange attractors" for the point location algorithm. A large number of test points located close to the boundary gets located in slivers, despite the fact that normally none of these points should fall in there. The number of points that the locate() method assigns to slivers is also totally out of proportion to the fraction of the outer shell occupied by the slivers.

So the impression is that the slivers are somehow fooling the location algorithm. Could it be that the "inside / outside" detection depends on the sign of some computed quantity (something related to a matrix determinant) and that in the case of slivers, the result should be "zero" but is not due to numerical errors and that the location algorithm then "concludes" that the point is inside the sliver -- which is not the case, just a results of bad conditionning ?

Is there a way to specify a threshold value for the quantity used to make the "inside / outside" test so that the problem related to slivers can be avoided ?

Regards,

Renaud

--

Renaud GILLON SYDELITY "Scaleable Virtual Prototyping" Mobile : +32 (0)495 27 65 65 E-mail : Web: www.sydelity.com

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss