Computing the external geodesic diameter of a simple polygon

D. Samuel, G. T. Toussaint

Research output: Contribution to journalArticlepeer-review


Given a simple polygon P of n vertices, we present an algorithm that finds the pair of points on the boundary of P that maximizes the external shortest path between them. This path is defined as the external geodesic diameter of P. The algorithm takes 0(n2) time and requires 0(n) space. Surprisingly, this problem is quite different from that of computing the internal geodesic diameter of P. While the internal diameter is determined by a pair of vertices of P, this is not the case for the external diameter. Finally, we show how this algorithm can be extended to solve the all external geodesic furthest neighbours problem.

Original languageEnglish (US)
Pages (from-to)1-19
Number of pages19
Issue number1
StatePublished - Mar 1990


  • AMS Subject Classifications: 68U05, 68C25
  • Polygon
  • algorithm
  • complexity
  • computational geometry
  • diameter
  • furthest neighbour
  • geodesics

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Computing the external geodesic diameter of a simple polygon'. Together they form a unique fingerprint.

Cite this