Combinatorial complexity bounds for arrangements of curves and spheres

Kenneth L. Clarkson, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Emo Welzl

Type: Article

Publication Date: 1990-03-01

Citations: 334

DOI: https://doi.org/10.1007/bf02187783

View Publication

Download PDF

Locations

Discrete & Computational Geometry - View - PDF

Similar Works

Action	Title	Year	Authors
+	Balanced Line Separators of Unit Disk Graphs	2017	Paz Carmi Man Kwun Chiu Matthew J. Katz Matias Korman Yoshio Okamoto André van Renssen Marcel Roeloffzen Taichi Shiitada Shakhar Smorodinsky
+	Balanced Line Separators of Unit Disk Graphs	2017	Paz Carmi Man Kwun Chiu Matthew J. Katz Matias Korman Yoshio Okamoto André van Renssen Marcel Roeloffzen Taichi Shiitada Shakhar Smorodinsky
+ PDF Chat	Improved Bounds for Incidences Between Points and Circles	2014	Micha Sharir Adam Sheffer Joshua Zahl
+ PDF Chat	Improved Lower Bound on the Number of Pseudoline Arrangements	2024	Justin Dallant
+ PDF Chat	Extremal problems on triangle areas in two and three dimensions	2009	Adrian Dumitrescu Micha Sharir Csaba D. Tóth
+	Hyperplane arrangements with large average diameter: a computational approach	2019	Antoine Deza Hiroyuki Miyata Sonoko Moriyama Feng Xie
+ PDF Chat	An Improved Constant Factor for the Unit Distance Problem	2022	Péter Ágoston Dömötör Pálvölgyi
+	The Complexity of Recognizing Geometric Hypergraphs	2023	Daniel Bertschinger Nicolas El Maalouly Linda Kleist Tillmann Miltzow Simon Weber
+	How do curved spheres intersect in 3-space?	2012	Sergey Avvakumov
+	An improved constant factor for the unit distance problem	2020	Péter Ágoston Dömötör Pálvölgyi
+ PDF Chat	Improved bounds for incidences between points and circles	2013	Micha Sharir Adam Sheffer Joshua Zahl
+ PDF Chat	Improved bounds for incidences between points and circles	2013	Micha Sharir Adam Sheffer Joshua Zahl
+ PDF Chat	Approximating Minimum Manhattan Networks in Higher Dimensions	2013	Aparna Das Emden R. Gansner Michael Kaufmann Stephen Kobourov Joachim Spoerhase Alexander Wolff
+	How do curved spheres intersect in 3-space?	2012	Sergey Avvakumov
+	Combinatorial and computational results for line arrangements in space	1989	Herbert Edelsbrunner
+	A note on the unit distance problem for planar configurations with $\mathbb{Q}$-independent direction set	2015	Mark Herman Jonathan Pakianathan
+	The Complexity of Recognizing Geometric Hypergraphs	2023	Daniel Bertschinger Nicolas El Maalouly Linda Kleist Tillmann Miltzow Simon Weber
+	An improved constant factor for the unit distance problem.	2020	Péter Ágoston Dömötör Pálvölgyi
+ PDF Chat	Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes	2011	Menelaos I. Karavelas Eleni Tzanaki
+	On Arrangements of Orthogonal Circles	2019	Steven Chaplick Henry Förster Myroslav Kryven Alexander Wolff

Works That Cite This (177)

Action	Title	Year	Authors
+ PDF Chat	A Crossing Lemma for Jordan curves	2018	János Pach Natan Rubin Gábor Tardos
+ PDF Chat	Cell Complexities in Hyperplane Arrangements	2004	Boris Aronov Micha Sharir
+ PDF Chat	Polytopes in Arrangements	2001	Boris Aronov Tamal K. Dey
+	Variations on the theme of repeated distances	1990	Péter L. Erdős János Pach
+ PDF Chat	Concentration estimates for algebraic intersections	2023	Miguel N. Walsh
+ PDF Chat	The polynomial method over varieties	2020	Miguel N. Walsh
+	Incidences of not-too-degenerate hyperplanes	2005	György Elekes Csaba D. Tóth
+	Unit distance problems	2015	Daniel M. Oberlin Richard Oberlin
+	Extremal Hypergraphs and Combinatorial Geometry	1995	Zoltán Füredi
+ PDF Chat	Fourier bases and a distance problem of Erd\H os	1999	Alex Iosevich Nets Hawk Katz Steen Pedersen

Works Cited by This (17)

Action	Title	Year	Authors
+	Unit distances in the Euclidean plane	1984	Joel Spencer Endre Szemerédi WT Trotter
+ PDF Chat	On some problems of elementary and combinatorial geometry	1975	P. Erdős
+ PDF Chat	Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs	1989	Fan Chung
+ PDF Chat	A Problem of Leo Moser About Repeated Distances on the Sphere	1989	P. Erdős Dean Hickerson János Pach
+	Applications of random sampling in computational geometry, II	1988	Kenneth L. Clarkson
+	On the maximal number of edges of many faces in an arrangement	1986	Herbert Edelsbrunner E Welzl
+	On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry	1983	József Beck
+	A theorem on arrangements of lines in the plane	1969	R. J. Canham
+	Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines	1980	Jacob E. Goodman Richard Pollack
+ PDF Chat	Repeated distances in space	1988	David Avis Paul Erdős János Pach