Combinatorial complexity bounds for arrangements of curves and spheres

DOI10.1007/BF02187783zbMATH Open0704.51003DBLPjournals/dcg/ClarksonEGSW90WikidataQ54309704 ScholiaQ54309704MaRDI QIDQ917017FDOQ917017

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

Publication date: 1990

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

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

Recommendations

• scientific article; zbMATH DE number 2145241
• Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs
• Unit distances
• Incidences between points and circles in three and higher dimensions
• Incidences between points and circles in three and higher dimensions

zbMATH Keywords

boundsarrangements of curvesarrangements of spheresmany-face problems

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On extremal problems of graphs and generalized graphs
• Research Problems in Discrete Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• \(\epsilon\)-nets and simplex range queries
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• The power of geometric duality
• Über ein Problem von K. Zarankiewicz
• On a problem of K. Zarankiewicz
• The complexity of many cells in arrangements of planes and related problems
• On Sets of Distances of n Points
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• Extremal problems in discrete geometry
• A sweepline algorithm for Voronoi diagrams
• Title not available (Why is that?)
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Topologically sweeping an arrangement
• The complexity and construction of many faces in arrangements of lines and of segments
• Proof of Grünbaum's conjecture on the stretchability of certain arrangements of pseudolines
• Title not available (Why is that?)
• On some problems of elementary and combinatorial geometry
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
• Title not available (Why is that?)
• Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
• Implicitly representing arrangements of lines or segments
• Cylindrical Algebraic Decomposition I: The Basic Algorithm
• Title not available (Why is that?)
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the maximal number of edges of many faces in an arrangement
• A theorem on arrangements of lines in the plane
• Triangles in space or building (and analyzing) castles in the air
• Title not available (Why is that?)
• A Problem of Leo Moser About Repeated Distances on the Sphere
• Title not available (Why is that?)
• Repeated distances in space
• Title not available (Why is that?)
• Sphere-and-point incidence relations in high dimensions with applications to unit distances and furthest-neighbor pairs
• On the Number of Furthest Neighbour Pairs in a Point Set

Cited In (only showing first 100 items - show all)

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

This page was built for publication: Combinatorial complexity bounds for arrangements of curves and spheres

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q917017)