Shortest Paths Help Solve Geometric Optimization Problems in Planar Regions

DOI10.1137/0221038zbMath0749.68093OpenAlexW2063244634MaRDI QIDQ4016400

Diane L. Souvaine, Elefterios A. Melissaratos

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 pathsimple polygonsroboticsvisibilityseparatorsinclusion problemsgeometric optimization problemsstock-cuttingsplinegonsenclosure problems

Mathematics Subject Classification ID

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

Related Items (11)

Finding a largest-area triangle in a terrain in near-linear time ⋮ An Algorithm to Compute Any Simple $k$-gon of a Maximum Area or Perimeter Inscribed in a Region of Interest ⋮ A tight bound for point guards in piecewise convex art galleries ⋮ Peeling Potatoes Near-Optimally in Near-Linear Time ⋮ Visibility graphs, dismantlability, and the cops and robbers game ⋮ Largest triangle inside a terrain ⋮ Largest triangles in a polygon ⋮ Multiple shooting approach for computing approximately shortest paths on convex polytopes ⋮ Shortest curves in planar regions with curved boundary ⋮ Quickest visibility queries in polygonal domains ⋮ Computing an \(L_1\) shortest path among splinegonal obstacles in the plane

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