Shortening Regions For a given set of points, there exists a
minimum weight triangulation. That is, there is a triangulation that
minimizes the sum of the edge lengths. For some triangulations, there
are zones where the total length of all edges can be reduced by adding
an additional point, and re-triangulating.
This point set can have it's total edge length for the minimum weight triangulation reduced by the addition of a point...
...such as here, for example.
Our task was to automate the finding of these regions.
Using a minimum-weight-triangulation finder provided by Jesus DeLoera of University of California, Davis, we generated a toolset to automate the finding of these shortening regions.
And Lo, there was a pretty picture
This is the shortening region of...
...this pointset. (Not to scale.)
How it works
Our script feeds many different version of a pointset
through the CPLEX solution program gifted by Dr. DeLoera, one for each
point we wish to check for shortening on addition, plus the original
case. The resulting logfile is then parsed and transformed into a webpage by a second script, producing a picture of the shortening zone.
Future ambitions include the solving of the minimum weight
triangulation without resorting to CPLEX, the software package that
DeLoera's code calls. This would allow the portability of the code to
computers without an existing CPLEX license. Also, our code currently
solves for the whether or not individual points are in the reducing
zone, not the boundaries of the reducing zones themselves. It is our
hope that this intermediate step, and the diagrams generated by it,
will help generate an intuition to guide a future proof of the nature
of shortening zones.
Cindy Traub, primary researcher
Sam Brown, codemonkey