scientific article; zbMATH DE number 1017008

zbMath0881.52001MaRDI QIDQ4339095

Publication date: 4 June 1997

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

arrangements packings convexity convex sets graph theory density combinatorial geometry coverings polygonal approximations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Exact enumeration problems, generating functions (05A15) Other designs, configurations (05B30) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02)

Related Items

Lower bounds for the chromatic numbers of distance graphs with large girth, Exact algorithms of searching for the largest size cluster in two integer 2-clustering problems, A semi-algebraic version of Zarankiewicz's problem, Almost similar configurations, On some monotone path problems in line arrangements, On the chromatic number of some geometric type Kneser graphs, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Counting and Cutting Rich Lenses in Arrangements of Circles, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, Discrete geometry on colored point sets in the plane -- a survey, Separating circles on the sphere by polygonal tilings, Connecting Cycles for Concentric Circles, A product inequality for extreme distances, Approximating set multi-covers, On the chromatic number of an infinitesimal plane layer, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, The smallest convex \(k\)-gon containing \(n\) congruent disks, Drawing outerplanar graphs using thirteen edge lengths, Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Estimate of the number of edges in special subgraphs of a distance graph, Harmonic functions of polynomial growth on infinite penny graphs, On the number of tangencies among 1-intersecting \(x\)-monotone curves, System of unbiased representatives for a collection of bicolorings, Constant-Factor Approximation for TSP with Disks, Approximating the k-Level in Three-Dimensional Plane Arrangements, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Large Unavoidable Subtournaments, On arrangements of orthogonal circles, On the Frankl–Rödl theorem, Random polytopes and the wet part for arbitrary probability distributions, Remarks on superstrings, fractal gravity, Nagasawa's diffusion and Cantorian spacetime, Vulnerability of nearest neighbor graphs, A combinatorial problem on polynomials and rational functions, Note on geometric graphs, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii, On the number of points in general position in the plane, Paul Erdős, 1913-1996, On the number of regular vertices of the union of Jordan regions, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, Colorings of the space \(\mathbb R^{n}\) with several forbidden distances, On packing \(\mathbb R^3\) with thin tori, Noncrossing monochromatic subtrees and staircases in 0-1 matrices, Packing and covering with centrally symmetric convex disks, Minimum vertex cover in ball graphs through local search, A combinatorial theorem on labeling squares with points and its application, The shortest distance among points in general position., On the number of regular vertices of the union of Jordan regions, Tight lower bounds for the size of epsilon-nets, One problem on geometric Ramsey numbers, Independent set of intersection graphs of convex objects in 2D, Nearly equal distances and Szemerédi's regularity lemma, The geometry of Minkowski spaces -- a survey. I, Inequalities between lattice packing and covering densities of centrally symmetric plane convex bodies, Erdös distance problem in vector spaces over finite fields, Radial points in the plane, A PTAS for a disc covering problem using width-bounded separators, Piercing all translates of a set of axis-parallel rectangles, On grids in point-line arrangements in the plane, Unnamed Item, Crossing patterns of segments, Unnamed Item, Can one define geometry today?, Crossing-free segments and triangles in point configurations, On threshold probability for the stability of independent sets in distance graphs, Centering koebe polyhedra via Möbius transformations, Discrete harmonic functions on infinite penny graphs, Edge Bounds and Degeneracy of Triangle-Free Penny Graphs and Squaregraphs, On the shortest separating cycle, On Grids in Point-Line Arrangements in the Plane, Edge integrity of nearest neighbor graphs and separator theorems, The number of edges in induced subgraphs of some distance graphs, New Turán type bounds for Johnson graphs, Six Topics on Inscribable Polytopes, On \(n\)-dependence, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, A lower bound on opaque sets, From harmonic analysis to arithmetic combinatorics, New upper bounds for the independence numbers of graphs with vertices in \(\{-1,0,1\}^n\) and their applications to problems of the chromatic numbers of distance graphs, Sets with few distinct distances do not have heavy lines, Traveling the boundary of Minkowski sums., Borsuk's problem and the chromatic numbers of metric spaces, Systems of distant representatives in Euclidean space, New upper bound for the chromatic number of a random subgraph of a distance graph, The packing density of the \(n\)-dimensional cross-polytope, An efficient \(k\) nearest neighbors searching algorithm for a query line., The Szemerédi-Trotter theorem in the complex plane, Covering the plane by a sequence of circular disks with a constraint, On large subgraphs with small chromatic numbers contained in distance graphs, The structure and number of global roundings of a graph, Dynamic coresets, Independence numbers of random subgraphs of a distance graph, Areas of triangles and Beck's theorem in planes over finite fields, Unavoidable crossings in a thinnest plane covering with congruent convex disks, On the diameter of separated point sets with many nearly equal distances, On the number of edges in induced subgraphs of a special distance graph, Independence numbers of random subgraphs of distance graphs, A new estimate for the number of edges in induced subgraphs of a special distance graph, Plane bichromatic trees of low degree, On the stabbing number of a random Delaunay triangulation, Spectral partitioning works: planar graphs and finite element meshes, Improved results on geometric hitting set problems, Noncrossing Hamiltonian paths in geometric graphs, The visible perimeter of an arrangement of disks, Diameters of random distance graphs, Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl, Plane graphs with straight edges whose bounded faces are acute triangles, Ball and spindle convexity with respect to a convex body, A center transversal theorem for hyperplanes and applications to graph drawing, On the approximability of covering points by lines and related problems, Theory and application of width bounded geometric separators, Relative \((p,\varepsilon )\)-approximations in geometry, An optimal generalization of the colorful Carathéodory theorem, On triangle cover contact graphs, Piercing translates and homothets of a convex body, Chromatic numbers of spaces with forbidden monochromatic triangles, On triple intersections of three families of unit circles, Realizability of graphs as triangle cover contact graphs, Piercing quasi-rectangles-on a problem of Danzer and Rogers, Periodicity of identifying codes in strips, Vertex partitions of non-complete graphs into connected monochromatic \(k\)-regular graphs, On levels in arrangements of surfaces in three dimensions, On distinct sums and distinct distances., Speeding up the incremental construction of the union of geometric objects in practice., Pointed drawings of planar graphs, Covering a rectangle with six and seven circles, An optimal extension of the centerpoint theorem, Sublinear time width-bounded separators and their application to the protein side-chain packing problem, The minimal volume of simplices containing a convex body, Packing, covering and tiling in two-dimensional spaces, Outerplanar thrackles, Approximating a convex body by a polytope using the epsilon-net theorem, Drawing outerplanar graphs using three edge lengths, Coloring intersection graphs of \(x\)-monotone curves in the plane, A non-linear lower bound for planar epsilon-nets, Improvements of the Frankl-Rödl theorem on the number of edges of a hypergraph with forbidden intersections, and their consequences in the problem of finding the chromatic number of a space with forbidden equilateral triangle, A new proof of Vázsonyi's conjecture, Problems related to a de Bruijn-Erdös theorem, Disjoint edges in topological graphs and the tangled-thrackle conjecture, On the number of similar instances of a pattern in a finite set, Separator theorems and Turán-type results for planar intersection graphs, Constrained versions of Sauer's Lemma, On the stability of some Erdős-Ko-Rado type results, Flips in planar graphs, The chromatic number of space with forbidden regular simplex, On the sum of distances along a circle, Incidences between points and generalized spheres over finite fields and related problems, Opaque sets, New results on the coarseness of bicolored point sets, \((m, n)\)-equidistant sets in \(\mathbb{R}^{k},\mathbb{S}^{k}\), and \(\mathbb P^k\), \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets, Oja centers and centers of gravity, Distance graphs with large chromatic numbers and small clique numbers, Gallai colorings of non-complete graphs, Antipodality properties of finite sets in Euclidean space, Centerpoints and Tverberg's technique, Almost empty monochromatic quadrilaterals in planar point sets, Unit distances and diameters in Euclidean spaces, A Ramsey-type result for geometric \(\ell\)-hypergraphs, A note on distinct distances in rectangular lattices, Hamiltonian paths in distance graphs, Maximum number of edges joining vertices on a cube, On the independence number of minimum distance graphs, Covering the plane with copies of a convex disk, On uniformly distributed dilates of finite integer sequences, Separable partitions, Bichromatic lines with few points, Distinct distances in planar point sets with forbidden 4-point patterns, An applied point pattern matching problem: Comparing 2D patterns of protein spots, On the longest spanning tree with neighborhoods, A new lower bound for the bipartite crossing number with applications, Extremal problems on triangle areas in two and three dimensions, Hitting sets when the VC-dimension is small, Cardinalities of \(k\)-distance sets in Minkowski spaces, A note on a problem of Erdős on right angles, Convexity and sumsets, Colouring proximity graphs in the plane, The multiplicity of the two smallest distances among points, Embedding a set of rational points in lower dimensions, Popular distances in 3-space, On the maximum number of touching pairs in a finite packing of translates of a convex body, On finding maximum-cardinality symmetric subsets, Monotone paths in line arrangements, On the combinatorics of projective mappings, Independence numbers and chromatic numbers of some distance graphs