Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons

DOI10.1109/TC.1983.1676186zbMATH Open0531.51002MaRDI QIDQ3312804FDOQ3312804

Authors:

Publication date: 1983

Published in: IEEE Transactions on Computers (Search for Journal in Brave)

Recommendations

• A linear time algorithm for the computation of some distance functions between convex polygons
• scientific article; zbMATH DE number 140463
• An optimal algorithm for solving collision distance between convex polygons in plane
• Computing the extreme distances between two convex polygons
• Finding the minimum vertex distance between two disjoint convex polygons in linear time

zbMATH Keywords

convex polygonintersection detection problemminimum distance between two polygons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Software, source code, etc. for problems pertaining to geometry (51-04)

Cited In (22)

• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• An optimal algorithm for finding the separation of simple polygons
• Title not available (Why is that?)
• A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram
• A unifying approach for a class of problems in the computational geometry of polygons
• Fuzzy distances for proximity characterization under uncertainty
• An iterative algorithm for finding a nearest pair of points in two convex subsets of \(\mathbb{R}^n\)
• An optimal algorithm for solving collision distance between convex polygons in plane
• Title not available (Why is that?)
• A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects
• A plane-sweep algorithm for finding a closest pair among convex planar objects
• Computing the intersection-depth to polyhedra
• An $O(E\log E + I)$ Expected Time Algorithm for the Planar Segment Intersection Problem
• On determining optimal strategies in pursuit games in the plane
• An approach to computing multipoint inversion and multiray surface intersection on parametric surface
• Finding the minimum vertex distance between two disjoint convex polygons in linear time
• An optimal algorithm for roundness determination on convex polygons
• Point inversion and projection for nurbs curve and surface: control polygon approach
• An algorithm for computing the distance between two circular disks
• A fast algorithm for the alpha-connected two-center decision problem
• The discrete and mixed minimax 2-center problems

This page was built for publication: Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons

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