Computing the extreme distances between two convex polygons
From MaRDI portal
Publication:3741079
DOI10.1016/0196-6774(85)90039-2zbMath0604.68079OpenAlexW2017260899MaRDI QIDQ3741079
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90039-2
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)
Related Items
Computation of penetration between smooth convex objects in three-dimensional space ⋮ Computing the intersection-depth to polyhedra ⋮ Shortest paths in the plane with convex polygonal obstacles ⋮ New variants of perfect non-crossing matchings ⋮ k-th shortest collision-free path planning ⋮ New results on binary space partitions in the plane (extended abstract) ⋮ Computing common tangents without a separating line ⋮ An optimal algorithm for finding the separation of simple polygons ⋮ A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects ⋮ Parallel algorithms for some functions of two convex polygons ⋮ Point inversion and projection for nurbs curve and surface: control polygon approach ⋮ A compact piecewise-linear Voronoi diagram for convex sites in the plane ⋮ A new fast algorithm for computing the distance between two disjoint convex polygons based on Voronoi diagram ⋮ New results on binary space partitions in the plane ⋮ \(\alpha\)-kernel problem with fuzzy visibility ⋮ A plane-sweep algorithm for finding a closest pair among convex planar objects ⋮ Fitting a two-joint orthogonal chain to a point set ⋮ Digital circles, spheres and hyperspheres: from morphological models to analytical characterizations and topological properties ⋮ New variants of perfect non-crossing matchings ⋮ Algorithms for weak and wide separation of sets ⋮ Spanning trees in multipartite geometric graphs ⋮ Data imprecision under \(\lambda\)-geometry model ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ Inscribing an axially symmetric polygon and other approximation algorithms for planar convex sets ⋮ A randomized incremental algorithm for the Hausdorff Voronoi diagram of non-crossing clusters ⋮ An approach to computing multipoint inversion and multiray surface intersection on parametric surface ⋮ On determining optimal strategies in pursuit games in the plane ⋮ Computing shortest transversals ⋮ A unifying approach for a class of problems in the computational geometry of polygons ⋮ An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons ⋮ COMPUTING CONSTRAINED SHORTEST SEGMENTS: BUTTERFLY WINGSPANS IN LOGARITHMIC TIME ⋮ Finding the minimum vertex distance between two disjoint convex polygons in linear time
