Thumbnail
Access Restriction
Subscribed

Author Pettie, Seth
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Combinatorics ♦ Forbidden patterns ♦ Sequences
Abstract One of the longest-standing open problems in computational geometry is bounding the complexity of the lower envelope of $\textit{n}$ univariate functions, each pair of which crosses at most $\textit{s}$ times, for some fixed $\textit{s}.$ This problem is known to be equivalent to bounding the length of an $order-\textit{s}$ Davenport-Schinzel sequence, namely, a sequence over an $\textit{n}-letter$ alphabet that avoids alternating subsequences of the form $\textit{a}$ &cdots; $\textit{b}$ &cdots; $\textit{a}$ &cdots; $\textit{b}$ &cdots; with length $\textit{s}+2.$ These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since been applied to bound the running times of geometric algorithms, data structures, and the combinatorial complexity of geometric arrangements. Let $Δ_{s}(n)$ be the maximum length of an $order-\textit{s}$ DS sequence over $\textit{n}$ letters. What is $Δ_{s}$ asymptotically? This question has been answered satisfactorily [Hart and Sharir 1986; Agarwal et al. 1989; Klazar 1999; Nivasch 2010], when $\textit{s}$ is even or $\textit{s}≤$ 3. However, since the work of Agarwal et al. in the mid-1980s, there has been a persistent gap in our understanding of the odd orders. In this work, we effectively close the problem by establishing sharp bounds on Davenport-Schinzel sequences of every order $\textit{s}.$ Our results reveal that, contrary to one's intuition, $Δ_{s}(n)$ behaves essentially like $Δ_{s-1}(n)$ when $\textit{s}$ is odd. This refutes conjectures by Alon et al. [2008] and Nivasch [2010].
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-11-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 5
Page Count 40
Starting Page 1
Ending Page 40


Open content in new tab

   Open content in new tab
Source: ACM Digital Library