Inradius.jl

The inradius of a curve is the radius of the largest sphere that lies inside of the curve’s convex hull. A long standing question has been: What is the shortest curve in $\mathbb R^3$ of inradius 1? This was recently solved for closed curves (see reference 1). For open curves this is still unsolved, however a conjecture from 2005 by Zalgaller still remains unbeaten (see reference 2).

I used this code in my PhD thesis (see reference 3) to provide numerical evidence that the Zalgaller conjecture is correct. I used the known solution for the closed curve to validate this method.

Example

Starting from the root folder of this repository, load the module via:

import Pkg; Pkg.activate(".")
include("src/Inradius.jl"); using .Inradius

To start from a random path defined by 8 points and go through 10 rounds of intermittent diffusion for each thread Julia is provided:

path = experiment(8, 10)

3×8 Matrix{Float64}:
  2.27767    0.426928  -0.587716  -0.697645  -0.240687   0.21088  -0.136078  -1.60925
 -0.923406  -1.4633    -1.20104   -0.277841   0.661854   1.35928   1.37428    0.68166
  0.321616   0.263964  -0.560367  -1.47404   -1.48406   -0.51342   0.77313    1.77003

then show the resulting length and inradius of the best path that has been found:

@show L(path); @show R(path);

L(path) = 10.129714236946846
R(path) = 1.0

We can start from this path if we want to continue to try and improve on the result:

path = experiment(8, 10, x = path)
@show L(path); @show R(path);

L(path) = 10.125103047486645
R(path) = 1.0000000000000002

We can see that we improved slightly by continuing.

Short explanation

I consider the space of paths defined by a finite list of points that are connected via line segments. For $N$ points, call the space of such paths $Ω_N$. The set of paths $\displaystyle \bigcup_N=1^∞Ω_N$ is dense in the space of all finite length paths, so this is a good discretization to use. Store those paths as $3 × N$ matrices where columns represent the points.

Because of the paths being defined by points connected by line segments, the convex hull of the path is also the convex hull of the defining points. Finding the convex hull of a point cloud is a well understood problem. From there, I use linear programming to solve the Chebyshev problem which gives the center and radius of the largest sphere in the convex hull.

Now that we have the types of paths we’re interested in and a way to calculate their inradii, I use global optimization by intermittent diffusion to find the optimum for a fixed number of points $N$. Do this for an increasing value $N$ and see if it’s converging. My thesis shows that this appears to converge quadratically both for the Zalgaller conjecture for open paths and for the known solution for closed paths.

References

1. Ghomi, M., & Wenk, J. (2021). Shortest closed curve to inspect a sphere. Journal für die reine und angewandte Mathematik. http://dx.doi.org/10.1515/crelle-2021-0049
2. Zalgaller, V. A. (2005). Shortest inspection curves for the sphere. Journal of Mathematical Sciences, 131(1), 5307–5320. http://dx.doi.org/10.1007/s10958-005-0403-9
3. See chapter 6 for the inradius problem, and section 6.3 specifically for the results in my thesis here