Combinatorics and algorithms of arrangements
The authors describe a way to deal with many computational problems arising in robotics, such as translating and rotating a polygon to fit into a bigger one, moving a polygonal robot among polygonal obstacles, performing ray-shooting on a terrain. All this motivates, as they show, the study of arrangements of low-degree algebraic surfaces in fixed- dimensional spaces. To bound the complexities of arrangements, a natural tool seems to be Davenport-Schinzel sequences [see e.g. \textit{P. Agarwal} and \textit{P. Shor}, J. Comb. Theory, Ser. A 52, No. 2, 228-274 (1984; Zbl 0697.05003)]. They show how to derive and apply such bounds, and recall the best known bounds (which are fairly complicated). To show how the bounds can be obtained, they provide a simple proof of the bound \(n \alpha (n)\) on the length of strings containing no substrings \(a \dots b \dots a \dots b \dots a\) (\(n\) is the size of the alphabet). This is the simplest nonlinear case for such sequences. Other tools such as geometric partitioning [see e.g. survey by \textit{P. Agarwal}, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 6, 1-37 (1991; Zbl 0733.68081)] are then presented, and yield combinatorial as well as algorithmic bounds for related arrangement problems. For the entire collection see [Zbl 0773.00009].
- Mathematical snapshots from the computational geometry landscape
- On the complexity of a single cell in certain arrangements of surfaces related to motion planning
- The complexity of the free space for a robot moving amidst fat obstacles
- A new technique for analyzing substructures in arrangements of piecewise linear surfaces
- Robot motion planning and the single cell problem in arrangements
- A near-quadratic algorithm for planning the motion of a polygon in a polygonal environment
- Algorithmic combinatorics based on slicing posets
- Harmonic functions for quadrilateral remeshing of arbitrary manifolds
- Combinatorial Properties of One-Dimensional Arrangements
- A recurrent algorithm for solving a combinatorial problem of arrangement with restrictions
- Robot motion planning
- scientific article; zbMATH DE number 1424290 (Why is no real title available?)
- Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications
This page was built for publication: Combinatorics and algorithms of arrangements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3138742)