On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

DOI10.1007/BF02187683zbMath0594.52004OpenAlexW1980092773WikidataQ56853078 ScholiaQ56853078MaRDI QIDQ1076976

János Pach, Micha Sharir, Klara Kedem, Ron A. Livné

Publication date: 1986

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

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

zbMATH Keywords

convex polygon Jordan curves motion planning polygonal obstacles collision- free translational motion point of local nonconvexity

Mathematics Subject Classification ID

Kinematics of mechanisms and robots (70B15) Inequalities and extremum problems involving convexity in convex geometry (52A40) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Related Items

LOCATING AN OBNOXIOUS LINE AMONG PLANAR OBJECTS, Space-aware reconfiguration, Clique-based separators for geometric intersection graphs, Decomposition of Multiple Packings with Subquadratic Union Complexity, On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves, Unnamed Item, ON THE EXPECTED SIZE OF THE 2D VISIBILITY COMPLEX, Searching for the closest-pair in a query translate, A randomized parallel algorithm for Voronoi diagrams based on symmetric convex distance functions, On the number of regular vertices of the union of Jordan regions, Unnamed Item, Polygon decomposition for efficient construction of Minkowski sums, Domination in Geometric Intersection Graphs, Combinatorial complexity of signed discs, Unnamed Item, Coloring intersection hypergraphs of pseudo-disks, Computing the smallest \(k\)-enclosing circle and related problems, Between shapes, using the Hausdorff distance, On pseudo-disk hypergraphs, Computing the intersection-depth to polyhedra, Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams, On the union complexity of families of axis-parallel rectangles with a low packing number, Approximate unions of lines and Minkowski sums, Finding Pairwise Intersections Inside a Query Range, Median trajectories, The Offset Filtration of Convex Objects, Improvements on geometric pattern matching problems, Piecewise linear paths among convex obstacles, Computing the smallest k-enclosing circle and related problems, COMPUTING PUSH PLANS FOR DISK-SHAPED ROBOTS, Inclusion-exclusion complexes for pseudodisk collections, On the two-dimensional Davenport-Schinzel problem, Coordinated motion planning for two independent robots, Motion planning in the presence of movable obstacles, A new efficient motion-planning algorithm for a rod in two-dimensional polygonal space, A crossing lemma for Jordan curves, Separating two simple polygons by a sequence of translations, Improved bounds on the Hadwiger-Debrunner numbers, A Polynomial-Time Algorithm for Computing Shortest Paths of Bounded Curvature Amidst Moderate Obstacles, The common exterior of convex polygons in the plane, 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects, The \(\varepsilon\)-\(t\)-net problem, The visibility-Voronoi complex and its applications, Combinatorial complexity of signed discs, A survey of motion planning and related geometric algorithms, Combinatorial complexity of translating a box in polyhedral 3-space, On fat partitioning, fat covering and the union size of polygons, Spanners for Directed Transmission Graphs, Deconstructing approximate offsets, On the union complexity of diametral disks, Getting around a lower bound for the minimum Hausdorff distance, On the number of touching pairs in a set of planar curves, Improved algorithms for placing undesirable facilities, Unnamed Item, On the union of cylinders in three dimensions, Near-linear approximation algorithms for geometric hitting sets, Tangencies between families of disjoint regions in the plane, Constant-Factor Approximation for TSP with Disks, Approximating the k-Level in Three-Dimensional Plane Arrangements, Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions, Improved approximation bounds for the minimum constraint removal problem, Optimization of the first Dirichlet Laplacian eigenvalue with respect to a union of balls, A procedure for computing the symmetric difference of regions defined by polygonal curves, Conflict-free coloring of intersection graphs of geometric objects, Coloring intersection hypergraphs of pseudo-disks, Combinatorial complexity bounds for arrangements of curves and spheres, Algorithmic aspects of proportional symbol maps, Approximation algorithms for maximum independent set of pseudo-disks, Speeding up the incremental construction of the union of geometric objects in practice., The upper envelope of piecewise linear functions: Algorithms and applications, Exact algorithms for the bottleneck Steiner tree problem, Union of random Minkowski sums and network vulnerability analysis, Constructing the relative neighborhood graph in 3-dimensional Euclidean space, A role of lower semicontinuous functions in the combinatorial complexity of geometric problems, On \(k\)-sets in arrangements of curves and surfaces, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Maximum Area Axis-Aligned Square Packings., Reaching a goal with directional uncertainty, Improved bounds on the union complexity of fat objects, On critical orientations in the Kedem-Sharir motion planning algorithm, The number of holes in the union of translates of a convex set in three dimensions, Intersection queries in sets of disks, On the number of regular vertices of the union of Jordan regions, A convex polygon among polygonal obstacle: Placement and high-clearance motion, Approximate motion planning and the complexity of the boundary of the union of simple geometric figures, Finding pairwise intersections inside a query range, Efficient hidden surface removal for objects with small union size, A note on the perimeter of fat objects, Optimizing a constrained convex polygonal annulus, Intersection queries in sets of disks, CONFLICT-FREE COLORINGS OF SHALLOW DISCS, Active-learning a convex body in low dimensions, On fat partitioning, fat covering and the union size of polygons, The Minkowski sum of a simple polygon and a segment, A note on smaller fractional Helly numbers, On the general motion-planning problem with two degrees of freedom, On arrangements of Jordan arcs with three intersections per pair, An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space, On regular vertices of the union of planar convex objects, Variations on the theme of repeated distances, The union of moving polygonal pseudodiscs -- combinatorial bounds and applications, Spheres, molecules, and hidden surface removal, On the number of critical free contacts of a convex polygonal object moving in two-dimensional polygonal space, Solving the irregular strip packing problem via guided local search for overlap minimization, Finding the \(\Theta \)-guarded region, Facility location problems in the plane based on reverse nearest neighbor queries, The reach of axis-aligned squares in the plane, One-way and round-trip center location problems, Robot motion planning and the single cell problem in arrangements, An optimal algorithm for reporting visible rectangles, AN ALGEBRA FOR SLOPE-MONOTONE CLOSED CURVES, Locating two obnoxious facilities using the weighted maximin criterion, On the complexity of a single cell in certain arrangements of surfaces related to motion planning, Translating a convex polyhedron over monotone polyhedra, An Output-Sensitive Convex Hull Algorithm for Planar Objects, FINDING THE LARGEST EMPTY DISK CONTAINING A QUERY POINT

Cites Work