# Computational Geometry Column 35

## Abstract

The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.

A natural shortest paths problem with many applications is: Given two points $`s`$ and $`t`$ on the surface of a polyhedron of $`n`$ vertices, find a shortest path on the surface from $`s`$ to $`t`$. This type of within-surface shortest path is often called a geodesic shortest path, in contrast to a Euclidean shortest path, which may leave the 2-manifold and fly through 3-space. Whereas finding a Euclidean shortest path is NP-hard \[CR87\], the geodesic shortest path may be found in polynomial time. After an early $`O(n^5)`$ algorithm \[OSB85\], an $`O(n^2\mathrm{log}n)`$ algorithm was developed that used a technique the authors dubbed the continuous Dijskstra method \[MMP87\]. This simulates the continuous propagation of a wavefront of points equidistant from $`s`$ across the surface, updating the wavefront at discrete events. It was another decade before this result was improved, by a clever $`O(n^2)`$ algorithm that does not track the wavefront \[CH96\]. This latter algorithm is simple enough to invite implementations, and several have appeared. Fig. 1 shows an example of using one implementation to find the shortest paths from $`s`$ to each vertex of a convex polyhedron.

Although other geometric shortest path problems saw the breaking of the quadratic barrier (see \[Mit97\]), paths on polyhedra resisted. One impediment is evident from Fig. 1: even on a convex polyhedron, there can be $`\mathrm{\Omega }(n^2)`$ crossings between polyhedron edges and paths to the vertices. So any algorithm that maintains these paths and treats edge-path crossings as events will be quadratic in the worst case. The continuous Dijskstra paradigm faces a similar dilemma: Examples exist for which there are $`\mathrm{\Omega }(n^2)`$ wavefront arc-edge crossings. These obstacles have recently been surmounted by a new algorithm by Sanjiv Kapoor that achieves $`O(n\mathrm{log}^2n)`$ time complexity \[Kap99\].

Kapoor’s algorithm follows the wavefront propagation method, and is surprisingly similar in overall structure to the original continuous Dijskstra algorithm \[MMP87\].

The algorithm maintains two primary geometric objects throughout the processing: the wavefront itself, $`W`$, which is a sequence of circular arcs, each centered on either $`s`$ or a vertex of the polyhedron (where paths may turn on nonconvex polyhedra); and a collection $`B`$ of boundary edges, edges of the polyhedron yet to be crossed by the wavefront. Both of these have size $`O(n)`$. Elements of $`W`$ and elements of $`B`$ are related and grouped by a nearest neighbor relation: $`eB`$ is associated with arc $`aW`$ if $`a`$ is closer to $`e`$ than to any other arc in $`W`$. Boundary edges associated with one arc are grouped into a boundary section, and arcs associated with one boundary edge are grouped into a wavefront section. It is this grouping that permits avoiding the quadratic number of arc-edge crossing events. The number of wavefront section-edge events is only $`O(n)`$.

There remains another quadratic quagmire to be skirted: Identifying the next event requires computing the distance from an edge to a wavefront potentially composed of $`n`$ arcs. Kapoor handles this by building a hierarchical convex hull structure for both the wavefront sections and the boundary sections. Subhulls are connected by tangent bridges; internal nodes store an “alignment angle” that represents the unfolding relationship between sibling hulls. These structures permit computing the distance between a $`W`$-section and a $`B`$-section in (essentially) logarithmic time. Updating the data structures consumes $`O(\mathrm{log}^2n)`$ amortized time per event, which leads to the final $`O(n\mathrm{log}^2n)`$ time complexity.

The details are formidable, and implementation will be a challenge. But the many applications and the significant theoretical improvement suggest implementations will follow eventually.