scientific article; zbMATH DE number 1424289
The authors survey the basic results on the Davenport-Schinzel sequences (DS-sequences) and discuss their applications to a variety of geometric problems. It is pointed out that DS-sequences provide very valuable tools in the analysis of combinatorial and algorithmic problems in geometry, and play a very important role in geometric problems involving arrangements of curves and surfaces. A sequence \(U= \{u_1,u_2,\dots, u_m\}\) of integers is an \((n,s)\) DS-sequence (\(n\), \(s\) being positive integers) if it satisfies the following conditions: (i) \(1\leq u_i\leq n\) for each \(i\leq m\), (ii) \(u_i\neq u_{i+1}\) for each \(i< m\), and (iii) there do not exist \(s+2\) indices \(1\leq i_1< i_2<\cdots< i_{s+2}\leq m\) such that \(u_{i_1}= u_{i_3}= u_{i_5}=\cdots= a\), \(u_{i_2}, u_{i_4}=\cdots= b\), where \(a\neq b\). The length of the sequence \(u\) is defined to be \(|U|= m\), \(s\) is called the order of \(U\), and \(m\) the number of symbols composing \(U\). The topics surveyed deal with showing the connection between DS-sequences and lower envelopes, discussing the analysis of the maximum length of \((n,s)\) DS-sequences, and presenting basic combinatorial geometric applications of DS-sequences to two-dimensional arrangements of lines, segments, and arcs. For the entire collection see [Zbl 0930.65001].
- Sharp bounds on Davenport-Schinzel sequences of every order
- scientific article; zbMATH DE number 1808181
- Three generalizations of Davenport-Schinzel sequences
- Enumeration of some Davenport-Schinzel sequences
- Almost linear upper bounds on the length of general Davenport-Schinzel sequences
- scientific article; zbMATH DE number 732977
- scientific article; zbMATH DE number 1341926
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- On numbers of Davenport-Schinzel sequences
- Enumerating Davenport-Schinzel sequences
- Ready, set, go! The Voronoi diagram of moving points that start from a line
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Generalized Davenport-Schinzel sequences
- Extremal problems for ordered (hyper)graphs: Applications of Davenport-Schinzel sequences
- Facility location problems with uncertainty on the plane
- Extremal problems for ordered hypergraphs: small patterns and some enumeration
- Color-spanning localized query
- Voronoi game on polygons
- Rearranging a sequence of points onto a line
- On the zone of the boundary of a convex body
- Shortest paths in time-dependent FIFO networks
- The geometry of Minkowski spaces -- a survey. II.
- On the two-dimensional Davenport-Schinzel problem
- Hide-and-seek: algorithms for polygon walk problems
- Shortest Path Problems on a Polyhedral Surface
- Link Distance and Shortest Path Problems in the Plane
- Enumerating Davenport-Schinzel sequences
- scientific article; zbMATH DE number 732977 (Why is no real title available?)
- Unions of fat convex polytopes have short skeletons
- Shortest path problems on a polyhedral surface
- Scandinavian thins on top of cake: new and improved algorithms for stacking and packing
- Maintaining Reeb graphs of triangulated 2-manifolds
- Minimizing the Weighted Directed Hausdorff Distance between Colored Point Sets under Translations and Rigid Motions
- Untangling planar graphs from a specified vertex position-Hard cases
- Enumeration of some Davenport-Schinzel sequences
- Link distance and shortest path problems in the plane
- Vehicle routing with time-dependent travel times: theory, practice, and benchmarks
- Interview with Micha Sharir
- Enclosing points with geometric objects
- Convex polygon containment: improving quadratic to near linear time
- A survey of exact and approximation algorithms for linear-parametric optimization problems
- A novel sequential method for building upper and lower bounds of moments of distributions
- Convex blocking and partial orders on the plane
- Capturing crossings: convex hulls of segment and plane intersections
- Largest empty circle centered on a query line
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4945501)
