On separating two simple polygons by a single translation

DOI10.1007/BF02187729zbMath0684.68063MaRDI QIDQ1825657

Yanyan Li

Publication date: 1989

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131078

zbMATH Keywords

FIND-PATH problem; moving polygons

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

52A10: Convex sets in (2) dimensions (including convex curves)

Related Items

Decomposing the boundary of a nonconvex polyhedron, Translating polygons with applications to hidden surface removal, Embedding Graphs into Embedded Graphs, Relative convex hulls in semi-dynamic arrangements, Decomposing the boundary of a nonconvex polyhedron, Computing minimum length paths of a given homotopy class, Assembly sequences for polyhedra, A polygonal approximation for general 4-contours corresponding to weakly simple curves, Embedding graphs into embedded graphs, On the separability of quadrilaterals in the plane by translations and rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Geodesic methods in quantitative image analysis
• Separating two simple polygons by a sequence of translations
• A linear algorithm for finding the convex hull of a simple polygon
• Traditional Galleries Require Fewer Watchmen
• On Removing a Ball without Disturbing the Others
• Euclidean shortest paths in the presence of rectilinear barriers
• Shortest path solves edge-to-edge visibility in a polygon
• Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Optimal Search in Planar Subdivisions