scientific article; zbMATH DE number 5486666

zbMath1157.52001MaRDI QIDQ5302610

János Pach, Micha Sharir

Publication date: 8 January 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

motion planningcrossing numbergraph drawinggeometric transversalshyperplane arrangementincidencesray shootingDavenport-Schinzel sequences15-puzzleextremal problems in geometrycutting lensesgeometric coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Erd?s problems and related topics of discrete geometry (52C10) Randomized algorithms (68W20) Graph representations (geometric and intersection representations, etc.) (05C62) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Combinatorial complexity of geometric structures (52C45)

Related Items (24)

Sparse hard-disk packings and local Markov chains ⋮ Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces ⋮ Unreliable point facility location problems on networks ⋮ On the maximum number of translates in a point set ⋮ A crossing lemma for Jordan curves ⋮ On sets defining few ordinary lines ⋮ Sparse locally-jammed disk packings ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Coboundary expansion, equivariant overlap, and crossing numbers of simplicial complexes ⋮ Combinatorics of intervals in the plane. I: Trapezoids ⋮ On the Richter–Thomassen Conjecture about Pairwise Intersecting Closed Curves ⋮ Improved complexity results for the robust mean absolute deviation problem on networks with linear vertex weights ⋮ On the degenerate crossing number ⋮ Lines avoiding balls in three dimensions revisited ⋮ An incidence theorem in higher dimensions ⋮ Unnamed Item ⋮ Helly-type theorems for approximate covering ⋮ On the number of similar instances of a pattern in a finite set ⋮ Homotheties and incidences ⋮ Limits of local search: quality and efficiency ⋮ Line transversals to disjoint balls ⋮ Some Discrete Properties of the Space of Line Transversals to Disjoint Balls ⋮ Unnamed Item ⋮ Dimensional lower bounds for Falconer type incidence theorems

This page was built for publication: