Geometric approximation algorithms

zbMATH Open1230.68215MaRDI QIDQ3010463FDOQ3010463

Authors: Sariel Har-Peled 

Publication date: 4 July 2011

Recommendations

• Computational geometry. Algorithms and applications.
• scientific article; zbMATH DE number 1220053
• scientific article; zbMATH DE number 1433426
• scientific article; zbMATH DE number 2038819
• scientific article; zbMATH DE number 3919830

zbMATH Keywords

samplingclusteringlinear programminggeometric approximation

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Combinatorial complexity of geometric structures (52C45)

Cited In (only showing first 100 items - show all)

• Influence-based Voronoi diagrams of clusters
• On separating points by lines
• Sublinear geometric algorithms
• Output sensitive algorithms for approximate incidences and their applications
• Near-optimal algorithms for the assortment planning problem under dynamic substitution and stochastic demand
• Routing on heavy-path WSPD-spanners
• Geometric Packing under Nonuniform Constraints
• \((\delta ,\varepsilon)\)-ball approximation of a shape: definition and complexity
• Fast local searches and updates in bounded universes
• Title not available (Why is that?)
• Optimal approximations made easy
• Title not available (Why is that?)
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• Title not available (Why is that?)
• Sparse convex hull coverage
• Sampling in combinatorial and geometric set systems
• The VC dimension of metric balls under Fréchet and Hausdorff distances
• Polynomial-sized topological approximations using the permutahedron
• Approximate polytope membership queries
• Window queries for intersecting objects, maximal points and approximations using coresets
• Approximating nearest neighbor distances
• Disjointness through the Lens of Vapnik-Chervonenkis Dimension: Sparsity and Beyond
• Near-linear time approximation schemes for geometric maximum coverage
• Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
• Metric spaces with expensive distances
• Two proofs for shallow packings
• A geometric buildup algorithm for the solution of the distance geometry problem using least-squares approximation
• On multiplicative \(\lambda\)-approximations and some geometric applications
• Title not available (Why is that?)
• Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
• Finding axis-parallel rectangles of fixed perimeter or area containing the largest number of points
• Nearest-neighbor searching under uncertainty. I
• Improved bounds for the expected number of \(k\)-sets
• Space exploration via proximity search
• Unsupervised assignment flow: label learning on feature manifolds by spatially regularized geometric assignment
• Computing the rectilinear center of uncertain points in the plane
• Dynamic smooth compressed quadtrees
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Conic nearest neighbor queries and approximate Voronoi diagrams
• Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
• From proximity to utility: a Voronoi partition of Pareto optima
• Partition of unity methods for signal processing on graphs
• Self-assignment flows for unsupervised data labeling on graphs
• Sparse Approximation via Generating Point Sets
• Journey to the Center of the Point Set
• A size-sensitive discrepancy bound for set systems of bounded primal shatter dimension
• On locality-sensitive orderings and their applications
• Approximating Minimization Diagrams and Generalized Proximity Search
• Subset selection for multiple linear regression via optimization
• On the combinatorial complexity of approximating polytopes
• Jaywalking your dog: computing the Fréchet distance with shortcuts
• Approximating length-restricted means under dynamic time warping
• Near-linear algorithms for geometric hitting sets and set covers
• Approximation algorithms for low-distortion embeddings into low-dimensional spaces
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• An algorithmic framework for the single source shortest path problem with applications to disk graphs
• A probabilistic approach to reducing algebraic complexity of Delaunay triangulations
• Spanners for directed transmission graphs
• Robust proximity search for balls using sublinear space
• Title not available (Why is that?)
• Bounds on the cost of compatible refinement of simplex decomposition trees in arbitrary dimensions
• On Locality-Sensitive Orderings and Their Applications
• Approximation algorithms for color spanning diameter
• Title not available (Why is that?)
• Preprocessing Ambiguous Imprecise Points
• Approximate range closest-pair queries
• Erdős-Hajnal conjecture for graphs with bounded VC-dimension
• The complexity of computing a bisimilarity pseudometric on probabilistic automata
• On the complexity of randomly weighted multiplicative Voronoi diagrams
• Title not available (Why is that?)
• Assignment flows
• Approximating the maximum overlap of polygons under translation
• Title not available (Why is that?)
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
• Adaptive deep Fourier residual method via overlapping domain decomposition
• A faster algorithm for truth discovery via range cover
• Title not available (Why is that?)
• Approximating Distance Measures for the Skyline
• Faster algorithms for growing prioritized disks and rectangles
• Dynamic connectivity in disk graphs
• Adaptive atlas of connectivity maps
• Scaling by subsampling for big data, with applications to statistical learning
• Title not available (Why is that?)
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Coresets for \((k, \ell ) \)-median clustering under the Fréchet distance
• Approximating the \(\lambda \)-low-density value
• Routing on heavy path WSPD spanners
• Approximating the smallest \(k\)-enclosing geodesic disc in a simple polygon
• Optimal algorithms for geometric centers and depth
• Quasi-uniform designs with optimal and near-optimal uniformity constant
• A note on stabbing convex bodies with points, lines, and flats
• General techniques for combinatorial approximation
• Online Spanners in Metric Spaces
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Title not available (Why is that?)
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Approximating maximum diameter-bounded subgraph in unit disk graphs
• Approximate range queries for clustering
• Title not available (Why is that?)
• Clustering with faulty centers

Uses Software

• CGAL

This page was built for publication: Geometric approximation algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010463)