Name
Abstract | ||
|---|---|---|
Let $H$ be a set of $n$ halfplanes in $mathbb{R}^2$ in general position, and let $ku003cn$ be a given parameter. We show that the number of vertices of the arrangement of $H$ that lie at depth exactly $k$ (i.e., that are contained in the interiors of exactly $k$ halfplanes of $H$) is $O(nk^{1/3} + n^{2/3}k^{4/3})$. The bound is tight when $k=Theta(n)$. This generalizes the study of Dey [Dey98], concerning the complexity of a single level in an arrangement of lines, and coincides with it for $k=O(n^{1/3})$. |
Year | Venue | Field |
|---|---|---|
2016 | arXiv: Computational Geometry | Discrete mathematics,Combinatorics,General position,Vertex (geometry),Arrangement of lines,Mathematics |
DocType | Volume | Citations |
Journal | abs/1609.07709 | 0 |
PageRank | References | Authors |
0.34 | 4 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sariel Har-Peled | 1 | 2630 | 191.68 |
| Micha Sharir | 2 | 8405 | 1183.84 |