Finding the minimum vertex distance between two disjoint convex polygons in linear time

DOI10.1016/0898-1221(85)90109-9zbMath0586.68060OpenAlexW2008745553WikidataQ126643835 ScholiaQ126643835MaRDI QIDQ1071519

Michael McKenna, Godfried T. Toussaint

Publication date: 1985

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(85)90109-9

zbMATH Keywords

algorithmworst-case time complexitylinearly separable convex polygonsminimum Euclidean distance

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99) Polytopes and polyhedra (52Bxx)

Related Items (2)

Finding a closet visible vertex pair between two polygons ⋮ An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

Cites Work

• Unnamed Item
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• The relative neighbourhood graph of a finite planar set
• On the multimodality of distances in convex polygons
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Complexity, convexity, and unimodality
• Computing the extreme distances between two convex polygons

This page was built for publication: Finding the minimum vertex distance between two disjoint convex polygons in linear time