Computing the geodesic diameter of a 3-polytope

ABSTRACT

We present an &Ogr;(n14 log n) algorithm for computing the geodesic diameter of a 3-polytope of n vertices. The geodesic diameter is the greatest separation between two points on the surface, where distance is determined by the shortest (geodesic) path between two points. We assume a model of computation that permits finding roots of a one-variable polynomial of fixed degree in constant time. The key geometric result underlying the algorithm is that, although it may be that neither endpoint of the diameter is a vertex of the polytope, when this occurs, there must be at least five distinct equal-length paths between the diameter endpoints.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory