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 work

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.

by
Cindy Traub, primary researcher
Sam Brown, codemonkey