Combinatorial complexity bounds for arrangements of curves and spheres

DOI10.1007/BF02187783zbMath0704.51003WikidataQ54309704 ScholiaQ54309704MaRDI QIDQ917017

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

Publication date: 1990

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/131110

zbMATH Keywords

bounds arrangements of curves arrangements of spheres many-face problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Coloring of graphs and hypergraphs (05C15) Combinatorial geometries and geometric closure systems (51D20)

Related Items

Improved Elekes-Szabó type estimates using proximity, Concentration estimates for algebraic intersections, Radial points in the plane, On lazy randomized incremental construction, Polynomial partitioning on varieties of codimension two and point-hypersurface incidences in four dimensions, From harmonic analysis to arithmetic combinatorics, On counting point-hyperplane incidences, On the Zarankiewicz problem for intersection hypergraphs, On joints in arrangements of lines in space and related problems, The Szemerédi-Trotter theorem in the complex plane, Many-face complexity in incremental convex arrangements, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Almost tight upper bounds for lower envelopes in higher dimensions, A semi-algebraic version of Zarankiewicz's problem, Incidences with Curves in ℝ d, Convex polygons made from few lines and convex decompositions of polyhedra, Unit Distances in Three Dimensions, On the diameter of separated point sets with many nearly equal distances, Triangles in space or building (and analyzing) castles in the air, Sphere tangencies, line incidences and Lie’s line-sphere correspondence, Rich cells in an arrangement of hyperplanes, Point sets with distinct distances, A crossing lemma for Jordan curves, A survey of mass partitions, Counting and Cutting Rich Lenses in Arrangements of Circles, The overlay of lower envelopes and its applications, Vertical decompositions for triangles in 3-space, The common exterior of convex polygons in the plane, MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS, Lines in space: Combinatorics and algorithms, Nondegenerate spheres in four dimensions, Furthest neighbours in space, Erdös distance problems in normed spaces, The exact fitting problem in higher dimensions, Distinct distances in finite planar sets, An improved bound on the number of unit area triangles, Erased arrangements of linear and convex decompositions of polyhedra, A note on visibility-constrained Voronoi diagrams, Finite point configurations in the plane, rigidity and Erdős problems, The number of unit distances is almost linear for most norms, On continuum incidence problems related to harmonic analysis., On the Number of Tetrahedra with Minimum, Unit, and Distinct Volumes in Three-Space, Polynomial effective density in quotients of \(\mathbb{H}^3\) and \(\mathbb{H}^2 \times \mathbb{H}^2\), Approximating the k-Level in Three-Dimensional Plane Arrangements, Distinct distances between points and lines, The polynomial method over varieties, Spanners for geodesic graphs and visibility graphs, On totally positive matrices and geometric incidences, Partitioning arrangements of lines. II: Applications, Bounding the number of \(k\)-faces in arrangements of hyperplanes, Euclidean minimum spanning trees and bichromatic closest pairs, On the Erdős distinct distances problem in the plane, On disjoint concave chains in arrangements of (pseudo) lines, Almost tight bounds for \(\epsilon\)-nets, Arrangements of curves in the plane --- topology, combinatorics, and algorithms, Repeated angles in the plane and related problems, Counting facets and incidences, The maximum number of second smallest distances in finite planar sets, Highly incidental patterns on a quadratic hypersurface in \(\mathbb{R}^4\), Applications of random sampling to on-line algorithms in computational geometry, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Counting and cutting cycles of lines and rods in space, Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom, Applications of a new space-partitioning technique, Forbidden paths and cycles in ordered graphs and matrices, The grid revisited, The number of edges of many faces in a line segment arrangement, Relative neighborhood graphs in three dimensions, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, Quasi-optimal upper bounds for simplex range searching and new zone theorems, Incidences between points and lines in \({\mathbb {R}}^4\), Incidence estimates for well spaced tubes, Nearly equal distances and Szemerédi's regularity lemma, Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, Facility location problems with uncertainty on the plane, The complexity and construction of many faces in arrangements of lines and of segments, The complexity of many cells in arrangements of planes and related problems, Point-curve incidences in the complex plane, A restriction estimate using polynomial partitioning, Non-Degenerate Spheres in Three Dimensions, Incidences with curves in \(\mathbb{R}^d\), Unit distances and diameters in Euclidean spaces, A Szemerédi-Trotter type theorem in \(\mathbb R^4\), On the general motion-planning problem with two degrees of freedom, Implicitly representing arrangements of lines or segments, Efficient randomized algorithms for some geometric optimization problems, New lower bounds for Hopcroft's problem, Variations on the theme of repeated distances, Graphs drawn with few crossings per edge, Spheres, molecules, and hidden surface removal, ALGORITHMS FOR POINT SET MATCHING WITH k-DIFFERENCES, Applications of random sampling in computational geometry. II, Geometric incidence theorems via Fourier analysis, On uniformly distributed dilates of finite integer sequences, Counting higher order tangencies for plane curves, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Extremal problems on triangle areas in two and three dimensions, Cardinalities of \(k\)-distance sets in Minkowski spaces, On distinct distances among points in general position and other related problems, Convexity and sumsets, Counting problems relating to a theorem of Dirichlet, Popular distances in 3-space, Distinct distances in the complex plane, Distinct distance estimates and low degree polynomial partitioning, On the sum of squares of cell complexities in hyperplane arrangements, Stability versus speed in a computable algebraic model

Cites Work