Combinatorial complexity bounds for arrangements of curves and spheres

DOI10.1007/BF02187783zbMath0704.51003DBLPjournals/dcg/ClarksonEGSW90WikidataQ54309704 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

boundsarrangements of curvesarrangements of spheresmany-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 (only showing first 100 items - show all)

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

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

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