On the average complexity of the $k$-level
$\newcommand{\LL}{\mathcal{L}}\newcommand{\SS}{\mathcal{S}}$Let \(\LL\) be an arrangement of \(n\) lines in the Euclidean plane. The \(k\)-level of \(\LL\) consists of all vertices \(v\) of the arrangement which have exactly \(k\) lines of \(\LL\) passing below \(v\). The complexity (the maximum siz...
Main Authors: | , , , , , |
---|---|
Format: | Article in Journal/Newspaper |
Language: | English |
Published: |
Journal of Computational Geometry
2020
|
Subjects: | |
Online Access: | https://jocg.org/index.php/jocg/article/view/3109 https://doi.org/10.20382/jocg.v11i1a19 |
id |
ftjocg:oai:ojs.library.carleton.ca:article/3109 |
---|---|
record_format |
openpolar |
spelling |
ftjocg:oai:ojs.library.carleton.ca:article/3109 2023-07-02T03:33:44+02:00 On the average complexity of the $k$-level Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel 2020-10-09 application/pdf https://jocg.org/index.php/jocg/article/view/3109 https://doi.org/10.20382/jocg.v11i1a19 eng eng Journal of Computational Geometry https://jocg.org/index.php/jocg/article/view/3109/2847 https://jocg.org/index.php/jocg/article/view/3109 doi:10.20382/jocg.v11i1a19 Copyright (c) 2020 Journal of Computational Geometry Journal of Computational Geometry; Vol. 11 No. 1 (2020); 493–506 1920-180X 10.20382/jocg.v11i1 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion 2020 ftjocg https://doi.org/10.20382/jocg.v11i1a1910.20382/jocg.v11i1 2023-06-12T12:07:59Z $\newcommand{\LL}{\mathcal{L}}\newcommand{\SS}{\mathcal{S}}$Let \(\LL\) be an arrangement of \(n\) lines in the Euclidean plane. The \(k\)-level of \(\LL\) consists of all vertices \(v\) of the arrangement which have exactly \(k\) lines of \(\LL\) 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 \(k\) to a marked cell, the south pole.We prove an upper bound of \(O((k+1)^2)\) on the expected complexity of the \((\le 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 \(d\)-sphere \(\SS^d\) which are orthogonal to a set of random points on \(\SS^d\). In this model, we prove that the expected complexity of the \(k\)-level is of order \(\Theta((k+1)^{d-1})\).In both scenarios, our bounds are independent of $n$, showing that the distribution of arrangements under our sampling methods differs significantly from other methods studied in the literature, where the bounds do depend on $n$. Article in Journal/Newspaper South pole Journal of Computational Geometry (JoCG - Carleton University, Computational Geometry Lab) South Pole |
institution |
Open Polar |
collection |
Journal of Computational Geometry (JoCG - Carleton University, Computational Geometry Lab) |
op_collection_id |
ftjocg |
language |
English |
description |
$\newcommand{\LL}{\mathcal{L}}\newcommand{\SS}{\mathcal{S}}$Let \(\LL\) be an arrangement of \(n\) lines in the Euclidean plane. The \(k\)-level of \(\LL\) consists of all vertices \(v\) of the arrangement which have exactly \(k\) lines of \(\LL\) 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 \(k\) to a marked cell, the south pole.We prove an upper bound of \(O((k+1)^2)\) on the expected complexity of the \((\le 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 \(d\)-sphere \(\SS^d\) which are orthogonal to a set of random points on \(\SS^d\). In this model, we prove that the expected complexity of the \(k\)-level is of order \(\Theta((k+1)^{d-1})\).In both scenarios, our bounds are independent of $n$, showing that the distribution of arrangements under our sampling methods differs significantly from other methods studied in the literature, where the bounds do depend on $n$. |
format |
Article in Journal/Newspaper |
author |
Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel |
spellingShingle |
Chiu, Man-Kwun Felsner, Stefan Scheucher, Manfred Schnider, Patrick Steiner, Raphael Valtr, Pavel On the average complexity of the $k$-level |
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 |
Journal of Computational Geometry |
publishDate |
2020 |
url |
https://jocg.org/index.php/jocg/article/view/3109 https://doi.org/10.20382/jocg.v11i1a19 |
geographic |
South Pole |
geographic_facet |
South Pole |
genre |
South pole |
genre_facet |
South pole |
op_source |
Journal of Computational Geometry; Vol. 11 No. 1 (2020); 493–506 1920-180X 10.20382/jocg.v11i1 |
op_relation |
https://jocg.org/index.php/jocg/article/view/3109/2847 https://jocg.org/index.php/jocg/article/view/3109 doi:10.20382/jocg.v11i1a19 |
op_rights |
Copyright (c) 2020 Journal of Computational Geometry |
op_doi |
https://doi.org/10.20382/jocg.v11i1a1910.20382/jocg.v11i1 |
_version_ |
1770273805764132864 |