ConvexHullMesh fails with small numbers

Question

When I try to get the ConvexHullMesh of a List of points that are "small scale", I get errors:

ConvexHullMesh[{{5.2041704279304214`*^-23,-2.0816681711721686`*^-23}, {-2.999999999999993`*^-8,-5.196152422706634`*^-8}, {3.000000000000005`*^-8, 5.19615242270663`*^-8}, {6.245004513516506`*^-23,-2.0816681711721686`*^-23}}]

"A Delaunay triangulation could not be found from the points"

and

"The function ConvexHullMesh is not implemented for".

Is that due to some precision issues? How can I have the Algorithm give me a correct solution?

Answer 1

Skip to the last section unless you have historical interest in my digging.

A quick Trace suggests a little of what may be going on.

The first step in the process is to call Region`Mesh`DeleteDuplicateCoordinates

expr = {{5.2041704279304214`*^-23, -2.0816681711721686`*^-23}, \
{-2.999999999999993`*^-8, -5.196152422706634`*^-8}, {3.000000000000005`*^-8, 
    5.19615242270663`*^-8}, {6.245004513516506`*^-23, -2.0816681711721686`*^-23}};

expr2 = Region`Mesh`DeleteDuplicateCoordinates[expr]

{{{5.9557*10^-23, -1.98523*10^-23}, {-3.*10^-8, -5.19615*10^-8},
 {3.*10^-8, 5.19615*10^-8}}, {1, 2, 3, 1}}

Almost immediately the first part of this is passed to DelaunayMesh which hands off to TriangleLink`TriangleDelaunay and trouble ensues:

TriangleLink`TriangleDelaunay @ expr2[[1]]

TriangleLink`TriangleDelaunay::trifc: A Delaunay triangulation could not be found from the points {{5.9557*10^-23,-1.98523*10^-23},{-3.*10^-8,-5.19615*10^-8},{3.*10^-8,5.19615*10^-8}}. >>

$Failed

Digging into that reveals a yet inner call:

TriangleLink`Private`iTriangleFun[{TriangleLink`TriangleDelaunay, 
  "-Q "}, {{5.955700410381799`*^-23, -1.9852334701272664`*^-23}, \
{-2.999999999999993`*^-8, -5.196152422706634`*^-8}, {3.000000000000005`*^-8, 
   5.19615242270663`*^-8}}]

This has a definition which can be read with:

Needs["GeneralUtilities`"]

PrintDefinitions @ TriangleLink`Private`iTriangleFun

I lost interest at this point, not finding any simple solution, but that might be a good place to start for anyone who cares to carry the baton.

---

Location of the error

Okay, I couldn't keep from wondering what happened next, which leads to this self contained example that returns a library error. Since I am not a low-level programmer I'll have to leave that to someone else, even if the library is readable.

Needs["TriangleLink`"]

pts = {{5.9557*10^-23, -1.98523*10^-23},
       {-3.*10^-8, -5.19615*10^-8},
       { 3.*10^-8,   5.19615*10^-8}};

inInst = TriangleCreate[];

TriangleSetPoints[inInst, TriangleLink`Private`pack[N[pts]]];

outInst = TriangleTriangulate[inInst, "-Q "];

TriangleGetSegments[outInst]

LibraryFunctionError["LIBRARY_FUNCTION_ERROR", 6]

Domain of the error

Although I could not probe deeper into a Trace I wondered what would come from exploring the domain of the error, meaning what values actually case an error and which do not. Following Quantum_Oli's comment I wanted to see what scaling did. Working with the inner function found above:

Needs["TriangleLink`"]

pts = {{5.955700410381799`*^-23, -1.9852334701272664`*^-23}, \
{-2.999999999999993`*^-8, -5.196152422706634`*^-8}, {3.000000000000005`*^-8, 
    5.19615242270663`*^-8}};

goodQ = Quiet[
    TriangleLink`Private`iTriangleFun[{TriangleLink`TriangleDelaunay, 
       "-Q "}, #] =!= $Failed] &;

And simple scaling by multiplying by the first twenty natural numbers:

r1 = Table[goodQ[i*pts], {i, 20}]

{False, False, True, False, True, True, True, False,
 True, True, True, True, True, True, True, False, True, True, True, True}

See the pattern? Let's make it obvious:

Position[r1, False]

{{1}, {2}, {4}, {8}, {16}}

Well that's funny indeed. Does it continue?

Or @@ Table[goodQ[ 2^i * pts ], {i, 500}]

False

Clearly scale is totally irrelevant; this has nothing to do with "small numbers" but instead is a pathological case that affects these particular numbers, and it is extremely sensitive!

goodQ[2^50.0000000000001*pts]
goodQ[2^50.0`*pts]
goodQ[2^49.9999999999999*pts]

True

False

True

I am now confident enough to assert that there is a bug here. However I cannot yet see why this inner function is highly sensitive yet the original example with ConvexHullMesh is not. I also question whether the "Location of the error" example is even correct as I truncated the inputs when I copied it to post here, yet the error message still occurs.