On the Average Complexity of the $k$-Level
Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{$k$-level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been wid...
Main Authors: | , , , , , |
---|---|
Format: | Article in Journal/Newspaper |
Language: | unknown |
Published: |
arXiv
2019
|
Subjects: | |
Online Access: | https://dx.doi.org/10.48550/arxiv.1911.02408 https://arxiv.org/abs/1911.02408 |
id |
ftdatacite:10.48550/arxiv.1911.02408 |
---|---|
record_format |
openpolar |
spelling |
ftdatacite:10.48550/arxiv.1911.02408 2023-05-15T18:22:03+02:00 On the Average Complexity of the $k$-Level Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel 2019 https://dx.doi.org/10.48550/arxiv.1911.02408 https://arxiv.org/abs/1911.02408 unknown arXiv arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ Computational Geometry cs.CG Combinatorics math.CO FOS Computer and information sciences FOS Mathematics G.2.1; I.3.5 52C30, 68Q25 Article CreativeWork article Preprint 2019 ftdatacite https://doi.org/10.48550/arxiv.1911.02408 2022-03-10T16:32:42Z Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{$k$-level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(n\cdot (k+1)^{1/3})$. Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the \emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$-spheres on the sphere $\mathbb{S}^d$ which are orthogonal to a set of random points on $\mathbb{S}^d$. In this model, we prove that the expected complexity of the $k$-level is of order $Θ((k+1)^{d-1})$. Article in Journal/Newspaper South pole DataCite Metadata Store (German National Library of Science and Technology) South Pole |
institution |
Open Polar |
collection |
DataCite Metadata Store (German National Library of Science and Technology) |
op_collection_id |
ftdatacite |
language |
unknown |
topic |
Computational Geometry cs.CG Combinatorics math.CO FOS Computer and information sciences FOS Mathematics G.2.1; I.3.5 52C30, 68Q25 |
spellingShingle |
Computational Geometry cs.CG Combinatorics math.CO FOS Computer and information sciences FOS Mathematics G.2.1; I.3.5 52C30, 68Q25 Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel On the Average Complexity of the $k$-Level |
topic_facet |
Computational Geometry cs.CG Combinatorics math.CO FOS Computer and information sciences FOS Mathematics G.2.1; I.3.5 52C30, 68Q25 |
description |
Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{$k$-level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(n\cdot (k+1)^{1/3})$. Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the \emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$-spheres on the sphere $\mathbb{S}^d$ which are orthogonal to a set of random points on $\mathbb{S}^d$. In this model, we prove that the expected complexity of the $k$-level is of order $Θ((k+1)^{d-1})$. |
format |
Article in Journal/Newspaper |
author |
Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel |
author_facet |
Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel |
author_sort |
Chiu, Man-Kwun |
title |
On the Average Complexity of the $k$-Level |
title_short |
On the Average Complexity of the $k$-Level |
title_full |
On the Average Complexity of the $k$-Level |
title_fullStr |
On the Average Complexity of the $k$-Level |
title_full_unstemmed |
On the Average Complexity of the $k$-Level |
title_sort |
on the average complexity of the $k$-level |
publisher |
arXiv |
publishDate |
2019 |
url |
https://dx.doi.org/10.48550/arxiv.1911.02408 https://arxiv.org/abs/1911.02408 |
geographic |
South Pole |
geographic_facet |
South Pole |
genre |
South pole |
genre_facet |
South pole |
op_rights |
arXiv.org perpetual, non-exclusive license http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
op_doi |
https://doi.org/10.48550/arxiv.1911.02408 |
_version_ |
1766201409005420544 |