People

At a Dagstuhl seminar in October 2003, Lars Kulik asked whether efficient line simplification could be achieved by a certain "shortcutting" operation (described below). Jack Snoeyink, Ryan Coleman, and Diane Souvaine at Tufts University have now developed such an algorithm. Craig Falls is implementing the algorithm and reporting on some practical considerations, comparing it to competing algorithms, etc. We will submit a paper Feb 21, 2005.

The Problem

Start with an arrangement of non-intersecting line segments (typically in the form of polygonal boundaries). Then, iteratively remove points, connecting their neighbors directly. (Shortcutting is only defined for degree-2 points -- degree-1 points can always be removed along with their lone edge, and higher-degree points are left alone.) However, doing so may introduce intersections with other line segments in the arrangement. So, the algorithm either reports that the shortcutting is not possible for that point, or it performs the shortcutting operation.

Our Solution

The runtime is O(n log n) pre-processing time on the initial arrangement and O(log^2 n) time per shortcut.

First approach: The algorithm works by first computing an x-monotone subdivision of the arrangement, and maintaining a dynamic convex hull of each x-monotone chain. Then, when a point is being deleted, only the x-monotone chain above and below the point needs to be inspected to determine if the triangle sweeped out by the shortcut operation is empty (and therefore doesn't change the homotopy). The problem with this approach is that we are unable to maintain an x-monotone subdivision with bounded vertex degree. Such subdivisions exist, but they are expensive to maintain. (I can provide examples upon request.)

New approach: Maintain a geodesic triangulation of the arrangement. A geodesic triangle on three vertices u, v, w is just the shortest path from u to v, v to w, and w to u. A balanced geodesic triangulation guarantees that a ray in the subidivision will intersect at most log(n) geodesic triangles. A balanced geodesic triangulation can be found for any connected planar subdivision but GIS data is often a disconnected subdivision, so we are looking for ways to maintain a connected subdivision by adding fake edges while maintaining bounded vertex degree.

For more information

More details are available in the attached rough draft of our paper. Please read it and offer comments.

-- CraigFalls - 02 Feb 2005

* main.ps: Postscript version of a preliminary draft paper
to top