On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences |
| |
Authors: | Timothy M Chan |
| |
Institution: | (1) School of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
| |
Abstract: | We give a surprisingly short proof that in any planar arrangement of n curves where each pair intersects at most a fixed number (s) of
times, the k-level has subquadratic (O(n2-1/2s) complexity. This answers one of the main open problems from the author’s previous paper DCG 29, 375-393 (2003)],
which provided a weaker upper bound for a
restricted class of curves only (graphs of degree-s polynomials).
When combined with existing tools (cutting curves, sampling, etc.),
the new idea generates a slew of improved k-level results for
most of the curve families studied earlier, including a
near-O(n3/2 bound for parabolas. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|