Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions

DOI10.1137/0221038MaRDI QIDQ4016400zbMATH OpenOpenAlexFDO

Authors Elefterios A. Melissaratos, Diane L. Souvaine

Publication date 14 December 1992

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/34f030c0a6e83975524f8bee6e7be0cb8157aac1

zbMATH Keywords

enclosure problemsgeometric optimization problemsinclusion problemsroboticsseparatorsshortest pathsimple polygonssplinegonsstock-cuttingvisibility

Mathematics Subject Classification ID

Geometric constructions in real or complex geometry (51M15) Approximation by convex sets (52A27) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10)

Recommendations

• Shortest polygonal paths in space
• On Shortest Paths in Polyhedral Spaces
• scientific article; zbMATH DE number 1424303
• Shortest paths in the plane with polygonal obstacles
• Optimal shortest path queries in a simple polygon

Cited in

(18)

• Shortest curves in planar regions with curved boundary
• Visibility graphs, dismantlability, and the cops and robbers game
• Computing an \(L_1\) shortest path among splinegonal obstacles in the plane
• Largest triangle inside a terrain
• Largest triangles in a polygon
• Quickest visibility queries in polygonal domains
• A tight bound for point guards in piecewise convex art galleries
• scientific article; zbMATH DE number 123833 (Why is no real title available?)
• scientific article; zbMATH DE number 2015319 (Why is no real title available?)
• scientific article; zbMATH DE number 1424303 (Why is no real title available?)
• An Algorithm to Compute Any Simple k-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest
• Multiple shooting approach for computing approximately shortest paths on convex polytopes
• Peeling potatoes near-optimally in near-linear time
• Voronoi-based splinegon decomposition and shortest-path tree computation
• Finding a largest-area triangle in a terrain in near-linear time
• Optimum turn-restricted paths, nested compatibility, and optimum convex polygons
• Shortest polygonal paths in space
• Finding a largest-area triangle in a terrain in near-linear time

This page was built for publication: Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions

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