Separating two simple polygons by a sequence of translations
From MaRDI portal
Publication:1104080
DOI10.1007/BF02187902zbMath0646.68052OpenAlexW2049742898MaRDI QIDQ1104080
Micha Sharir, Shmuel Sifrony, Richard Pollack
Publication date: 1988
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131041
Computational geometryoptimal algorithminverse Ackermann functionseparating polygons. translational separability of planar objects
Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20) Convex sets in (2) dimensions (including convex curves) (52A10) Geometric constructions in real or complex geometry (51M15)
Related Items
Arrangements of segments that share endpoints: Single face results, Assembly sequences for polyhedra, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Triangles in space or building (and analyzing) castles in the air, Coordinated motion planning for two independent robots, On the separability of quadrilaterals in the plane by translations and rotations, A survey of motion planning and related geometric algorithms, Enumerating Davenport-Schinzel sequences, On the boundary of a union of Rays, Storing line segments in partition trees, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, An optimal algorithm for the boundary of a cell in a union of rays, The upper envelope of piecewise linear functions: Algorithms and applications, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, On movable separability and isotheticity, Partitioning a planar assembly into two connected parts is NP-complete, The number of edges of many faces in a line segment arrangement, Quasi-optimal upper bounds for simplex range searching and new zone theorems, The complexity and construction of many faces in arrangements of lines and of segments, On lazy randomized incremental construction, On the general motion-planning problem with two degrees of freedom, On arrangements of Jordan arcs with three intersections per pair, Detecting geometric infeasibility, On separating two simple polygons by a single translation, Robot motion planning and the single cell problem in arrangements, On the zone of the boundary of a convex body, On the complexity of assembly partitioning, On the complexity of a single cell in certain arrangements of surfaces related to motion planning, The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
Cites Work
- Unnamed Item
- Unnamed Item
- Visibility and intersection problems in plane geometry
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
- An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- A linear time algorithm for minimum link paths inside a simple polygon
- Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
