Sharp bounds on Davenport-Schinzel sequences of every order

DOI10.1145/2462356.2462390zbMath1305.68093arXiv1204.1086OpenAlexW2963302403MaRDI QIDQ5174492

Seth Pettie

Publication date: 17 February 2015

Published in: Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.1086

zbMATH Keywords

lower envelopesDavenport-Schinzel sequences

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Sequences (mod (m)) (11B50) Extremal combinatorics (05D99)

Related Items (9)

Kinetic \(k\)-semi-Yao graph and its applications ⋮ Three Generalizations of Davenport--Schinzel Sequences ⋮ Forbidden formations in multidimensional 0-1 matrices ⋮ On the zone of a circle in an arrangement of lines ⋮ On the zone of a circle in an arrangement of lines ⋮ Disjoint edges in topological graphs and the tangled-thrackle conjecture ⋮ A relationship between generalized Davenport-Schinzel sequences and interval chains ⋮ A simple, faster method for kinetic proximity problems ⋮ On the complexity of randomly weighted multiplicative Voronoi diagrams

This page was built for publication: Sharp bounds on Davenport-Schinzel sequences of every order