An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

Research output: Contribution to journalArticlepeer-review

Abstract

Let P={p1, p2, ..., pm} and Q={q1, q2, ..., qn} be two intersecting convex polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m+n) algorithm is presented for computing the minimum euclidean distance betweena vertex pi in P and a vertex qj in Q.

Original languageEnglish (US)
Pages (from-to)357-364
Number of pages8
JournalComputing
Volume32
Issue number4
DOIs
StatePublished - Dec 1984

Keywords

  • Algorithms
  • Voronoi diagrams
  • complexity
  • computational geometry
  • convex polygons
  • minimum distance

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons'. Together they form a unique fingerprint.

Cite this