Separating two simple polygons by a sequence of translations
DOI10.1007/BF02187902zbMATH Open0646.68052OpenAlexW2049742898MaRDI QIDQ1104080FDOQ1104080
Authors: Micha Sharir, Richard Pollack, Shmuel Sifrony 
Publication date: 1988
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131041
Recommendations
Computational geometryoptimal algorithminverse Ackermann functionseparating polygons. translational separability of planar objects
Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Polyhedra and polytopes; regular figures, division of spaces (51M20) Geometric constructions in real or complex geometry (51M15)
Cites Work
- Title not available (Why is that?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A linear time algorithm for minimum link paths inside a simple polygon
- Visibility and intersection problems in plane geometry
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams
- 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
- Title not available (Why is that?)
- A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space
- Erratum: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
Cited In (38)
- On lazy randomized incremental construction
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- On the complexity of one-shot translational separability.
- On the zone of the boundary of a convex body
- On the boundary of a union of Rays
- A survey of motion planning and related geometric algorithms
- The number of edges of many faces in a line segment arrangement
- Storing line segments in partition trees
- On the complexity of assembly partitioning
- Coordinated motion planning for two independent robots
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Separability by two lines and by nearly straight polygonal chains
- Detecting geometric infeasibility
- The complexity and construction of many faces in arrangements of lines and of segments
- Enumerating Davenport-Schinzel sequences
- Assembly sequences for polyhedra
- On movable separability and isotheticity
- On the general motion-planning problem with two degrees of freedom
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Separating a polyhedron by one translation from a set of obstacles
- An optimal algorithm for the boundary of a cell in a union of rays
- The upper envelope of piecewise linear functions: Algorithms and applications
- On the separability of quadrilaterals in the plane by translations and rotations
- Triangles in space or building (and analyzing) castles in the air
- Robot motion planning and the single cell problem in arrangements
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- On separating two simple polygons by a single translation
- Arrangements of segments that share endpoints: Single face results
- Subtraction of two 2D polygons with some matching vertices
- Title not available (Why is that?)
- Optimizing a Strip Separating Two Polygons
- Partitioning a planar assembly into two connected parts is NP-complete
- On arrangements of Jordan arcs with three intersections per pair
This page was built for publication: Separating two simple polygons by a sequence of translations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1104080)
