Combinatorics and algorithms of arrangements

From MaRDI portal





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].











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)