Separating two simple polygons by a sequence of translations
From MaRDI portal
Let P and Q be two disjoint simple (not necessarily convex) polygons. The authors present an algorithm which determines whether Q can be moved by a sequence of translations to a position sufficiently far from P without colliding with P, and which produces such a motion if it exists. For earlier research on translational separability of planar objects, see \textit{G. T. Toussaint}, Computational geometry, Mach. Intell. Pattern Recognition 2, 335-375 (1985; Zbl 0588.68053).
Recommendations
Cites work
- A linear time algorithm for minimum link paths inside a simple polygon
- 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
- Erratum: An O(n\log \log n)-Time Algorithm for Triangulating a Simple Polygon
- scientific article; zbMATH DE number 3911704 (Why is no real title available?)
- scientific article; zbMATH DE number 3945379 (Why is no real title available?)
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space
- 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
- Visibility and intersection problems in plane geometry
Cited in
(41)- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- A survey of motion planning and related geometric algorithms
- Arrangements of curves in the plane --- topology, combinatorics, and algorithms
- On movable separability and isotheticity
- The number of edges of many faces in a line segment arrangement
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- 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 the complexity of assembly partitioning
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- Coordinated motion planning for two independent robots
- On separating two simple polygons by a single translation
- Robot motion planning and the single cell problem in arrangements
- On the complexity of one-shot translational separability.
- Separability by two lines and by nearly straight polygonal chains
- Arrangements of segments that share endpoints: Single face results
- Assembly sequences for polyhedra
- On the zone of the boundary of a convex body
- On the separability of quadrilaterals in the plane by translations and rotations
- Subtraction of two 2D polygons with some matching vertices
- Triangles in space or building (and analyzing) castles in the air
- scientific article; zbMATH DE number 3905323 (Why is no real title available?)
- scientific article; zbMATH DE number 3945379 (Why is no real title available?)
- scientific article; zbMATH DE number 4049041 (Why is no real title available?)
- Enumerating Davenport-Schinzel sequences
- Optimizing a Strip Separating Two Polygons
- Intersection removal for simple polygons
- scientific article; zbMATH DE number 4121493 (Why is no real title available?)
- On the boundary of a union of Rays
- The complexity and construction of many faces in arrangements of lines and of segments
- On lazy randomized incremental construction
- Separating a polyhedron by one translation from a set of obstacles
- Partitioning a planar assembly into two connected parts is NP-complete
- Enclosing points with geometric objects
- On two-handed planar assembly partitioning with connectivity constraints
- The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis
- 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
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)
