Title: Davenport–Schinzel Sequences and Their Geometric Applications**Both authors have been supported by a grant from the U.S.–Israeli Binational Science Foundation. Pankaj Agarwal has also been supported by a National Science Foundation Grant CCR-93–01259, by an Army Research Office MURI grant DAAH04-96-1–0013, by a Sloan fellowship, and by an NYI award and matching funds from Xerox Corporation. Micha Sharir has also been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck …
Abstract: An (n, s) Davenport–Schinzel sequence, for positive integers n and s, is a sequence composed of n distinct symbols with the properties that no two adjacent elements are equal, and that it does not contain, as a (possibly non-contiguous) subsequence, any alternation a⋯b⋯a⋯b⋯ of length s + 2 between two distinct symbols a and b. The close relationship between Davenport–Schinzel sequences and the combinatorial structure of lower envelopes of collections of functions make the sequences very attractive because a variety of geometric problems can be formulated in terms of lower envelopes. A near-linear bound on the maximum length of Davenport–Schinzel sequences enable us to derive sharp bounds on the combinatorial structure underlying various geometric problems, which in turn yields efficient algorithms for these problems.
Publication Year: 2000
Publication Date: 2000-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 12
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot