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

DOI10.1007/BF02243778zbMATH Open0528.65005OpenAlexW1507258608MaRDI QIDQ786507FDOQ786507

Authors: Godfried Toussaint 

Publication date: 1984

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02243778

zbMATH Keywords

algorithmscomplexitycomputational geometryminimum distanceconvex polygonsVoronoi diagrams

Mathematics Subject Classification ID

Polytopes and polyhedra (52Bxx) Algorithms for approximation of functions (65D15)

Cites Work

• A new linear algorithm for intersecting convex polygons
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Computing the extreme distances between two convex polygons
• The all nearest-neighbor problem for convex polygons
• A note on the all nearest-neighbor problem for convex polygons
• Finding the minimum vertex distance between two disjoint convex polygons in linear time
• Optimal algorithms for computing the minimum distance between two finite planar sets

Cited In (14)

• New variants of perfect non-crossing matchings
• On determining the on-line minimax linear fit to a discrete point set in the plane
• Polygonal chain approximation: A query based approach
• A simple linear algorithm for intersecting convex polygons
• Optimal placement of convex polygons to maximize point containment
• Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set
• Finding a closet visible vertex pair between two polygons
• New variants of perfect non-crossing matchings
• Object and image indexing based on region connection calculus and oriented matroid theory
• Translating a convex polygon to contain a maximum number of points.
• Extremal point queries with lines and line segments and related problems
• Polygonal path simplification with angle constraints
• Finding the minimum vertex distance between two disjoint convex polygons in linear time
• Triangulations, visibility graph and reflex vertices of a simple polygon

This page was built for publication: An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786507)