Publication:3514515
From MaRDI portal
zbMath1155.52017MaRDI QIDQ3514515
János Pach, Pankaj K. Agarwal, Micha Sharir
Publication date: 21 July 2008
roboticscombinatorial complexityVoronoi diagramsmolecular modelingconstructive geometryproximity problemsfat trianglesconflict-free coloringsfat setssmall-size \(\varepsilon\)-netsunion in a set of geometric objects
Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Combinatorial complexity of geometric structures (52C45)
Related Items
On the complexity of barrier resilience for fat regions and bounded ply, Elastic geometric shape matching for translations under the Manhattan norm, Between shapes, using the Hausdorff distance, On the union complexity of families of axis-parallel rectangles with a low packing number, Quasi-Polynomial Time Approximation Scheme for Weighted Geometric Set Cover on Pseudodisks and Halfspaces, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, Improved bounds on the Hadwiger-Debrunner numbers, Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs, The \(\varepsilon\)-\(t\)-net problem, Homothetic polygons and beyond: maximal cliques in intersection graphs, On the union of cylinders in three dimensions, Near-linear approximation algorithms for geometric hitting sets, Tangencies between families of disjoint regions in the plane, Near-Optimal Lower Bounds for ε-Nets for Half-Spaces and Low Complexity Set Systems, Optimization of the first Dirichlet Laplacian eigenvalue with respect to a union of balls, Conflict-free coloring of intersection graphs of geometric objects, Lines avoiding balls in three dimensions revisited, Unions of fat convex polytopes have short skeletons, Unnamed Item, Approximation algorithms for maximum independent set of pseudo-disks, Unnamed Item, Union of random Minkowski sums and network vulnerability analysis, Union of Hypercubes and 3D Minkowski Sums with Random Sizes., The number of holes in the union of translates of a convex set in three dimensions, Limits of local search: quality and efficiency, \(\varepsilon\)-Mnets: Hitting geometric set systems with subsets, Union of hypercubes and 3D Minkowski sums with random sizes, Unnamed Item, A note on smaller fractional Helly numbers, Local search strikes again: PTAS for variants of geometric covering and packing, Abstract Voronoi Diagrams from Closed Bisecting Curves, Stochastic makespan minimization in structured set systems