On the shortest paths between two convex polyhedra

DOI10.1145/42282.214094zbMath0652.68043OpenAlexW2067305605MaRDI QIDQ3798231

Avikam Baltsan, Micha Sharir

Publication date: 1988

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/42282.214094

zbMATH Keywords

Voronoi diagramcomputational geometryEuclidean shortest pathDavenport-Schinzel sequencesinverse of Ackermann's functionconvex polyhedral

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (3) dimensions (including convex surfaces) (52A15) Discrete mathematics in relation to computer science (68R99)

Related Items

Planar realizations of nonlinear Davenport-Schinzel sequences by segments, On the geodesic Voronoi diagram of point sites in a simple polygon, Improved lower bounds on the length of Davenport-Schinzel sequences, A survey of motion planning and related geometric algorithms, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences