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

shortest pathvisibilityroboticsseparatorsinclusion problemsgeometric optimization problemsstock-cuttingsimple polygonssplinegonsenclosure problems

Mathematics Subject Classification ID

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

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

(16)

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

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)