Arrangements of curves in the plane --- topology, combinatorics, and algorithms
From MaRDI portal
Publication:1185003
DOI10.1016/0304-3975(92)90319-BzbMath0747.68094OpenAlexW4210528429WikidataQ126296231 ScholiaQ126296231MaRDI QIDQ1185003
Raimund Seidel, János Pach, Richard Pollack, Leonidas J. Guibas, Micha Sharir, Herbert Edelsbrunner
Publication date: 28 June 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90319-b
Related Items
Between shapes, using the Hausdorff distance ⋮ Castles in the air revisited ⋮ Selecting distances in the plane ⋮ The optimal tenement allocation for reducing traffic burden ⋮ Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications ⋮ Almost tight upper bounds for the single cell and zone problems in the three dimensions ⋮ Robust mean absolute deviation problems on networks with linear vertex weights ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Three dimensional weak visibility: Complexity and applications ⋮ Embeddability of arrangements of pseudocircles and graphs on surfaces ⋮ Convex blocking and partial orders on the plane ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ Characterization and computation of feasible trajectories for an articulated probe with a variable-length end segment ⋮ A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane ⋮ Shortcut sets for plane Euclidean networks (extended abstract) ⋮ The upper envelope of Voronoi surfaces and its applications ⋮ AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE ⋮ Design and analysis of planar shape deformation ⋮ Efficient on-line algorithms for Euler diagram region computation ⋮ THREE-DIMENSIONAL TOPOLOGICAL SWEEP FOR COMPUTING ROTATIONAL SWEPT VOLUMES OF POLYHEDRAL OBJECTS ⋮ Polygonal chains cannot lock in 4D ⋮ Model-based segmentation and classification of trajectories ⋮ ON COMPUTING TRANSLATIONAL SWEPT VOLUMES ⋮ Balanced line separators of unit disk graphs ⋮ Finding the \(\Theta \)-guarded region ⋮ Searching for equilibrium positions in a game of political competition with restrictions ⋮ Facility location problems in the plane based on reverse nearest neighbor queries ⋮ Three-dimensional weak visibility: Complexity and applications ⋮ One-way and round-trip center location problems ⋮ Robot motion planning and the single cell problem in arrangements ⋮ Shortcut sets for the locus of plane Euclidean networks ⋮ Weak visibility queries of line segments in simple polygons ⋮ COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET ⋮ Stability versus speed in a computable algebraic model
Cites Work
- Unnamed Item
- The complexity and construction of many faces in arrangements of lines and of segments
- 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
- Combinatorial complexity bounds for arrangements of curves and spheres
- On a circle placement problem
- On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
- The power of geometric duality
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Separating two simple polygons by a sequence of translations
- Improved lower bounds on the length of Davenport-Schinzel sequences
- Topologically sweeping an arrangement
- On the general motion-planning problem with two degrees of freedom
- On the two-dimensional Davenport-Schinzel problem
- Triangles in space or building (and analyzing) castles in the air
- On the “piano movers'” problem I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Sorting jordan sequences in linear time using level-linked search trees
