scientific article; zbMATH DE number 1749054

zbMath0999.52006MaRDI QIDQ4530626

Publication date: 4 June 2002

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

arrangements polyhedra convex sets transversals combinatorial geometry convex polytopes geometric configurations

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Other problems of combinatorial convexity (52A37) Research exposition (monographs, survey articles) pertaining to convex and discrete geometry (52-02)

Related Items

Tighter estimates for $\epsilon$-nets for disks, On the Zarankiewicz problem for intersection hypergraphs, Random sampling in computational algebra: Helly numbers and violator spaces, Error bounds for consistent reconstruction: random polytopes and coverage processes, On resilient graph spanners, A lower bound on the crossing number of uniform hypergraphs, Essential sign change numbers of full sign pattern matrices, Characterizing isometries on the order polytope with an application to the theory of fuzzy measures, Stabbing simplices by points and flats, Cuttings for disks and axis-aligned rectangles in three-space, Coarse differentiation and multi-flows in planar graphs, An inequality for distances between $2n$ points and the Aleksandrov--Rassias problem, A note on the colorful fractional Helly theorem, Pythagorean powers of hypercubes, Metric embedding, hyperbolic space, and social networks, Geometric drawings of $K_{n}$ with few crossings, VC dimensions of principal component analysis, Hitting simplices with points in $\mathbb R^{3}$, Improved results on geometric hitting set problems, Improved enumeration of simple topological graphs, Testing additive integrality gaps, A multivariate Gnedenko law of large numbers, A note on light geometric graphs, A new upper bound for the VC-dimension of visibility regions, On high-dimensional acyclic tournaments, Euclidean embeddings of finite metric spaces, The number of extreme points of tropical polyhedra, VC-dimension of perimeter visibility domains, Empirical risk minimization for heavy-tailed losses, Domination in transitive colorings of tournaments, A note about weak $\epsilon $-nets for axis-parallel boxes in $d$-space, Space lower bounds for low-stretch greedy embeddings, Low-distortion embeddings of graphs with large girth, Optimal partition trees, On feasible sets for MPC and their approximations, Sharp support recovery from noisy random measurements by $\ell_1$-minimization, An optimal generalization of the colorful Carathéodory theorem, Dynamic vs. oblivious routing in network design, On the optimality of gluing over scales, Tight bounds on the maximum size of a set of permutations with bounded VC-dimension, On levels in arrangements of surfaces in three dimensions, Diameters, distortion, and eigenvalues, Splitting full matrix algebras over algebraic number fields., Coding and counting arrangements of pseudolines, Indexability, concentration, and VC theory, Pivot selection: dimension reduction for distance-based indexing, Polychromatic coloring for half-planes, An incidence theorem in higher dimensions, On multiple-instance learning of halfspaces, An optimal extension of the centerpoint theorem, Union of random Minkowski sums and network vulnerability analysis, Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups, On the least trimmed squares estimator, On the construction of a family of transversal subspaces over finite fields, Optimal queue-size scaling in switched networks, Vertical versus horizontal Poincaré inequalities on the Heisenberg group, On affine maps on non-compact convex sets and some characterizations of finite-dimensional solid ellipsoids, A non-linear lower bound for planar epsilon-nets, A geometric proof of the colored Tverberg theorem, Discrete and lexicographic Helly-type theorems, On average distortion of embedding metrics into the line, Lipschitz factorization through subsets of Hilbert space, The degree of point configurations: Ehrhart theory, Tverberg points and almost neighborly polytopes, Disjoint edges in topological graphs and the tangled-thrackle conjecture, Some variations on Tverberg's theorem, Cutting planes from extended LP formulations, Discrete Voronoi games and $\epsilon$-nets, in two and three dimensions, Tverberg partitions of points on the moment curve, On the Beer index of convexity and its variants, Universal rigidity of complete bipartite graphs, Quantitative combinatorial geometry for continuous parameters, VC-sets and generic compact domination, On three measures of non-convexity, Positive-fraction intersection results and variations of weak epsilon-nets, Limits of local search: quality and efficiency, $\varepsilon$-Mnets: Hitting geometric set systems with subsets, A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces, Oja centers and centers of gravity, A note on the number of different inner products generated by a finite set of vectors, Computing hereditary convex structures, Prodsimplicial-neighborly polytopes, Uneven splitting of ham sandwiches, Tropical polar cones, hypergraph transversals, and mean payoff games, The Euclidean distortion of the lamplighter group., An application of shadow systems to Mahler's conjecture, Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique, Asymptotic theory for statistics of the Poisson-Voronoi approximation, Incidences with curves in $\mathbb{R}^d$, A linear-time algorithm for the geodesic center of a simple polygon, Two proofs for shallow packings, A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes, Separation with restricted families of sets, Eigenvectors of random matrices: A survey, A Ramsey-type result for geometric $\ell$-hypergraphs, Bounds for Pach's selection theorem and for the minimum solid angle in a simplex, A variant of the Hadwiger-Debrunner $(p,q)$-problem in the plane, Distinct distances in planar point sets with forbidden 4-point patterns, Simultaneous smoothness and simultaneous stability of a $C^\infty$ strictly convex integrand and its dual, An FPTAS for the volume of some $\mathcal{V} $-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes, Low dimensional embeddings of doubling metrics, Sketching and Embedding are Equivalent for Norms, On the Erdős-Szekeres convex polygon problem, Polygons with Prescribed Angles in 2D and 3D, The Parametric Closure Problem, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, A survey of mass partitions, METRIC INEQUALITIES, DISTORTION IN THE FINITE DETERMINATION RESULT FOR EMBEDDINGS OF LOCALLY FINITE METRIC SPACES INTO BANACH SPACES, Unique Covering Problems with Geometric Sets, Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem, Presburger Arithmetic, Rational Generating Functions, and Quasi-Polynomials, Journey to the Center of the Point Set, Lossless Prioritized Embeddings, ON PARAMETERIZED COMPLEXITY OF HITTING SET PROBLEM FOR AXIS–PARALLEL SQUARES INSTERSECTING A STRAIGHT LINE, Intersection Graphs of Rays and Grounded Segments, On Center Regions and Balls Containing Many Points, Unnamed Item, Unnamed Item, Expander graphs and their applications, Improved Bounds for Incidences Between Points and Circles, One-Sided Epsilon-Approximants, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, On embeddings of finite subsets of ℓ_{𝑝}, Unnamed Item, Unnamed Item, Unnamed Item, Colorful theorems for strong convexity, Euclidean distortion and the sparsest cut, An inequality for distances among five points and distance preserving mappings, A PTAS for the Steiner Forest Problem in Doubling Metrics, THE ERDŐS–SZEKERES PROBLEM AND AN INDUCED RAMSEY QUESTION, A COUNTEREXAMPLE TO A CONJECTURE OF LARMAN AND ROGERS ON SETS AVOIDING DISTANCE 1, Helly’s theorem: New variations and applications, A Friendly Smoothed Analysis of the Simplex Method, On the zone of a circle in an arrangement of lines, Approximating Tverberg points in linear time for any fixed dimension, On the zone of a circle in an arrangement of lines, Penalized multidimensional fitting for protein movement detection, Approximating Nonnegative Polynomials via Spectral Sparsification, Union of Hypercubes and 3D Minkowski Sums with Random Sizes., Robust Tverberg and Colourful Carathéodory Results via Random Choice, RAMSEY GROWTH IN SOME NIP STRUCTURES, Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős-Falconer distance conjecture, The Martin Gardner Polytopes, Maximum and minimum entropy states yielding local continuity bounds, Bourgain discretization using Lebesgue-Bochner spaces, A quantitative metric differentiation theorem, On the number of points in general position in the plane, Persistent homology for low-complexity models, Compression bounds for wreath products, On the VC-dimension, covering and separating properties of the cycle and spanning tree hypergraphs of graphs, Hitting and Piercing Rectangles Induced by a Point Set, Unnamed Item, An Almost Optimal Algorithm for Computing Nonnegative Rank, Non-representability of finite projective planes by convex sets, Erdös distance problem in vector spaces over finite fields, Some Discrete Properties of the Space of Line Transversals to Disjoint Balls, Snowflake universality of Wasserstein spaces, On a problem of Danzer, Complex interpolation between Hilbert, Banach and operator spaces, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Tverberg’s theorem is 50 years old: A survey, Unnamed Item, A Tverberg type theorem for matroids, Unnamed Item, The spherical dual transform is an isometry for spherical Wulff shapes, Counting faces of randomly projected polytopes when the projection radically lowers dimension, Weakly Modular Graphs and Nonpositive Curvature, Applications of the regularity lemma for uniform hypergraphs, Computing the Ehrhart quasi-polynomial of a rational simplex, Approximability of the Problem of Finding a Vector Subset with the Longest Sum, On a Problem of Danzer, Unnamed Item, Retracting Graphs to Cycles, Broadcasting Automata and Patterns on ℤ2, Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs, Unnamed Item, Separators in region intersection graphs, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Unnamed Item, Unnamed Item, On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$, Tverberg theorems over discrete sets of points, On the Stretch Factor of Polygonal Chains, Near Isometric Terminal Embeddings for Doubling Metrics, From harmonic analysis to arithmetic combinatorics, Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs, Unnamed Item, All finite sets are Ramsey in the maximum norm, Unnamed Item, Polygons with Prescribed Angles in 2D and 3D, The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich, Optimal Algorithms for Geometric Centers and Depth, Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance Functions, The Grazing Goat and Spherical Curiosities, Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis, Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors, Computational aspects of the Gromov-Hausdorff distance and its application in non-rigid shape matching, On the rectilinear crossing number of complete uniform hypergraphs, Metric Characterizations of Some Classes of Banach Spaces, A semi-algebraic version of Zarankiewicz's problem, Approximation and inapproximability results for maximum clique of disc graphs in high dimensions, Carathéodory, Helly and the others in the max-plus world, Limitations to Fréchet's metric embedding method, A note on approximation of a ball by polytopes, On some monotone path problems in line arrangements, Cutting algebraic curves into pseudo-segments and applications, Near equipartitions of colored point sets, How to play hot and cold, The VC-dimension of K-vertex D-polytopes, Outer normal transforms of convex polytopes, Tverberg-type theorems with altered intersection patterns (nerves), Carathéodory's theorem in depth, Approximating maximum diameter-bounded subgraph in unit disk graphs, Near isometric terminal embeddings for doubling metrics, Convex analysis in groups and semigroups: a sampler, Generically globally rigid graphs have generic universally rigid frameworks, Bracketing numbers of convex and $m$-monotone functions on polytopes, On the $k$-means/median cost function, On embeddings of locally finite metric spaces into $\ell_p$, A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model, Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning, Erdős-Hajnal conjecture for graphs with bounded VC-dimension, Further consequences of the colorful Helly hypothesis, A crossing lemma for multigraphs, 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, On partial cubes, well-graded families and their duals with some applications in graphs, New lower bounds for Tverberg partitions with tolerance in the plane, On a characterization of lattice cubes via discrete isoperimetric inequalities, Theorems of Carathéodory, Helly, and Tverberg without dimension, The right acute angles problem?, Characterizing unpredictable patterns in wireless sensor network data, Berge's theorem, fractional Helly, and art galleries, The Schur-Erdős problem for semi-algebraic colorings, Homogeneous selections from hyperplanes, On the 2-colored crossing number, Conflict-free coloring of intersection graphs of geometric objects, From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices, Higher-order Erdős-Szekeres theorems, Analysis and design of discrete-time linear systems with nested actuator saturations, Random polytopes and the wet part for arbitrary probability distributions, On random generation of fuzzy measures, A proof of the Oja depth conjecture in the plane, Real-reward testing for probabilistic processes, Large cliques in hypergraphs with forbidden substructures, Equivelar toroids with few flag-orbits, On the speed of algebraically defined graph classes, Upper bounds for stabbing simplices by a line, On the 3-distortion of a path, A simple proof for open cups and caps, Optimal distortion embeddings of distance regular graphs into Euclidean spaces, On discrete Brunn-Minkowski and isoperimetric type inequalities, Quantitative fractional Helly and $(p,q)$-theorems, A combinatorial property of points and balls, a colored version, Counting with rational generating functions, Colourful and fractional $(p,q)$-theorems, Dimension reduction by random hyperplane tessellations, Covering paths for planar point sets, An optimal randomized algorithm for $d$-variate zonoid depth, Isometric embedding of Busemann surfaces into $L_1$, Recursive geometry of the flow complex and topology of the flow complex filtration, Inequalities for distances between points and distance preserving mappings, Unnamed Item, An ordinal evaluation of categorical judgement data by random utilities and a corresponding correlation analysis, Adjacency on the order polytope with applications to the theory of fuzzy measures, The isotropic constant of random polytopes with vertices on convex surfaces, Vapnik-Chervonenkis density in some theories without the independence property, I, Bottom-up: a new algorithm to generate random linear extensions of a poset, A Danzer set for axis parallel boxes, The number of disk graphs, A positive fraction mutually avoiding sets theorem, Common transversals in the plane: The fractional perspective, On some covering problems in geometry, Book Review: Metric embeddings: bilipschitz and coarse embedddings into Banach spaces, Computing a Nonnegative Matrix Factorization---Provably, Large Area Convex Holes in Random Point Sets, Cutting lemma and Zarankiewicz's problem in distal structures, Constructions for the Elekes-Szabó and Elekes-Rónyai problems, Planar lattices and equilateral polygons, The Erdős-Szekeres Problem, Kirszbraun-type theorems for graphs, The Arithmetic Tutte polynomial of two matrices associated to Trees, Embeddability of locally finite metric spaces into Banach spaces is finitely determined, Faster algorithms for growing prioritized disks and rectangles, Probabilistic pursuits on graphs, Metric structures in $L_1$: dimension, snowflakes, and average distortion, Packing plane spanning graphs with short edges in complete geometric graphs, Integer cells in convex sets, Counting and representing intersections among triangles in three dimensions, Sunflowers of convex open sets, Monotone maps, sphericity and bounded second eigenvalue, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Topology of geometric joins, Sets with few distinct distances do not have heavy lines, Optimal bounds for the colored Tverberg problem, On Lipschitz extension from finite subsets, On piercing numbers of families satisfying the $(p,q)_{r}$ property, On the complexity of barrier resilience for fat regions and bounded ply, Optimal approximations made easy, Drawing the Horton set in an integer grid of minimum size, On the union complexity of families of axis-parallel rectangles with a low packing number, Geometric clustering in normed planes, Gaussian random projections for Euclidean membership problems, Noisy tensor completion via the sum-of-squares hierarchy, Analysis of classifiers' robustness to adversarial perturbations, Vertical perimeter versus horizontal perimeter, On the number of edges of separated multigraphs, Barycentric gluing and geometry of stable metrics, Disjointness through the lens of Vapnik-Chervonenkis dimension: sparsity and beyond, On the number of hyperedges in the hypergraph of lines and pseudo-discs, Neural networks with linear threshold activations: structure and algorithms, The $\varepsilon$-$t$-net problem, Tukey depth histograms, $k$-sets and rectilinear crossings in complete uniform hypergraphs, The crossing number of locally twisted cubes $L T Q_n$, $N$-step energy of maps and the fixed-point property of random groups., Uniform approximation of Vapnik-Chervonenkis classes, Coverings: variations on a result of Rogers and on the epsilon-net theorem of Haussler and Welzl, Entropy of convex functions on $\mathbb R^d$, Only distances are required to reconstruct submanifolds, A center transversal theorem for hyperplanes and applications to graph drawing, Rigid ball-polyhedra in Euclidean 3-space, On the computation of zone and double zone diagrams, Point sets with small integer coordinates and no large convex polygons, Helly numbers of algebraic subsets of $\mathbb{R}^{d}$ and an extension of Doignon's theorem, Colorful linear programming, Nash equilibrium, and pivots, Combinatorial generalizations of Jung's theorem, Contact graphs of unit sphere packings revisited, Modular groups in Cantorian $E^{(\infty)}$ high-energy physics., Kleinian groups in $E^{(\infty)}$ and their connection to particle physics and cosmology., Ramsey numbers and monotone colorings, Covering lattice points by subspaces and counting point-hyperplane incidences, The minimal volume of simplices containing a convex body, Computing solutions of the multiclass network equilibrium problem with affine cost functions, Approximating a convex body by a polytope using the epsilon-net theorem, On Grünbaum type inequalities, Lines in Euclidean Ramsey theory, Fast approximation of betweenness centrality through sampling, Asymptotic estimates for the largest volume ratio of a convex body, On the number of maximum empty boxes amidst $n$ points, Packing and covering with non-piercing regions, Computational aspects of the colorful Carathéodory theorem, The convexification effect of Minkowski summation, Halfspace depth and floating body, Beta polytopes and Poisson polyhedra: $f$-vectors and angles, Algebraic methods in the congested clique, Sets of large dimension not containing polynomial configurations, Quantitative $(p, q)$ theorems in combinatorial geometry, Centerpoints and Tverberg's technique, Reconstruction of atomic measures from their halfspace depth, Union of hypercubes and 3D Minkowski sums with random sizes, Radon numbers and the fractional Helly theorem, Uniform convergence of Vapnik-Chervonenkis classes under ergodic sampling, Function and colorful extensions of the KKM theorem, Approximate centerpoints with proofs, Randomly removing $g$ handles at once, Categorization generated by extended prototypes -- an axiomatic approach, Reconstruction of the crossing type of a point set from the compatible exchange graph of noncrossing spanning trees, Active-learning a convex body in low dimensions, The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem, Minimum ranks of sign patterns and zero-nonzero patterns and point-hyperplane configurations, A general incidence bound in $\mathbb{R}^d$, Strong independence and the dimension of a Tverberg set, Applying Young diagrams to 2-symmetric fuzzy measures with an application to general fuzzy measures, Planar point sets determine many pairwise crossing segments, Topological sweep of the complete graph, Topological obstructions for vertex numbers of Minkowski sums, Eppstein's bound on intersecting triangles revisited, Random Gale diagrams and neighborly polytopes in high dimensions, On the number of topological types occurring in a parameterized family of arrangements, On the number of Birch partitions, Monte Carlo cubature construction, Some recollections on early work with Jan Pelant, Volume distortion for subsets of Euclidean spaces, A new lower bound on Hadwiger-Debrunner numbers in the plane, On a class of Diophantine equations related to the numbers of cells in hyperplane arrangements, Small weak epsilon-nets, Resilient distributed vector consensus using centerpoint, Embedding dimension phenomena in intersection complete codes, Bounded $VC$-dimension implies the Schur-Erdős conjecture, Free disposal hull condition to verify when efficiency coincides with weak efficiency, Exact multi-covering problems with geometric sets, Hitting sets when the VC-dimension is small, Dimension gaps between representability and collapsibility, A framework for pursuit evasion games in, On the transversal number and VC-dimension of families of positive homothets of a convex body, Equipartitioning by a convex 3-fan, Some implications of interval approach to dimension for network complexity, Many order types on integer grids of polynomial size, Correlations of random classifiers on large data sets, Geometric and o-minimal Littlewood-Offord problems, Introduction to the combinatorial atlas, Learning with cone-based geometric models and orthologics, Primal and dual combinatorial dimensions, Arrangements of approaching pseudo-lines, Computing Shapley values in the plane, A Model for Birdwatching and other Chronological Sampling Activities, A note on stabbing convex bodies with points, lines, and flats, Stochastic approximation of lamplighter metrics, Improved bounds for the expected number of $k$-sets, Sloshing, Steklov and corners: Asymptotics of Steklov eigenvalues for curvilinear polygons, Least distortion Euclidean embeddings of flat tori, Graph-theoretic approaches for analyzing the resilience of distributed control systems: a tutorial and survey, Holes and islands in random point sets, Tight bounds on the expected number of holes in random point sets, Maximum rectilinear crossing number of uniform hypergraphs, Clique-based separators for geometric intersection graphs, The constant of point-line incidence constructions, Consequences and extensions of the Brunn-Minkowski theorem, Optimal controller synthesis for timed systems, Support vector machines and Radon's theorem, Correlation-based sparse inverse Cholesky factorization for fast Gaussian-process inference, Turning Grain Maps into Diagrams, Approximating length-restricted means under dynamic time warping, Shortest coordinated motion for square robots, Additive structure in convex translates, Unnamed Item, Unnamed Item, Advances in metric embedding theory, Intersecting convex sets by rays, Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond, New algorithms and bounds for halving pseudolines, Algorithms for Radon partitions with tolerance, Distributed construction of purely additive spanners, Permutrees, Arrangements of pseudocircles: on circularizability, A tight bound on approximating arbitrary metrics by tree metrics, Bregman Voronoi diagrams, Complexity and algorithms for finding a subset of vectors with the longest sum, On Erdős-Szekeres-type problems for $k$-convex point sets, On the integrality gap of binary integer programs with Gaussian data, Local search strikes again: PTAS for variants of geometric covering and packing, Robust shape fitting via peeling and grating coresets