[Octave-bug-tracker] [bug #60818] delaunayn - 2D code path vectorization doesn't match nD algorithm

[Nicholas Jankowski]

Follow-up Comment #19, bug #60818 (project octave):

regarding sliver identification, a few references:

"Generating Well-Shaped Delaunay Meshes in 3D" - Li & Teng [1]
- defines (for 3D) small as V/L^3 < tol1, where L is the smallest edge, AND
R/L < tol2, where R is the circumradius of the tetrahedron
Explained in his thesis [2] "Many types of tetrahedra can have a small value
of V/L3, but only slivers simultaneously have small R/L ratio". Much of his
work then goes into bounding tol1 and tol2, in addition to modifying the
delaunay process in the first place to avoid them.

[1] http://www.cs.iit.edu/~xli/paper/Conf/sliver-SODA01.pdf
[2]
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.7943&rep=rep1&type=pdf

"An experimental study of sliver exudation" - Edelsbrunner & Guoy [3]
Slivers have circumradius/min(L) approaching the right tetrahedral minimum of
sqrt(6)/4, but also 'small' minimum dihedral angle (between faces). (of course
calculating dihedral angles is a much larger set of vector products than we're
already doing. see [4])

[3]
https://www.ljll.math.upmc.fr/~frey/papers/meshing/Edelsbrunner%20H.,%20An%20experimental%20study%20of%20sliver%20exudation.pdf
[4] https://math.stackexchange.com/q/315171



At the moment the current patch uses V/L^n < 1000eps, for the explicit calcs,
so the direct solvers are doing part of the first criteria.

The nD portion is doing something like:
nth_root(vol) / (ndims *num_triangles)  < 100 eps

(allowing for equal R's, that's something like R^n = vol of a simplex).  I'm
still not following what the (ndims*numtriangles) part is intending, and why
the number of triangles should affect the size check. If we could make this
more of a relative size check (maybe doing a R / min(L) < tol^(1/n) for each
simplex?) it would be more consistent with the other check. 

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?60818>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/