| Publication | Date of Publication | Type |
|---|
| Approximate shape fitting via linearization | 2026-05-08 | Paper |
| Clustering motion | 2026-05-08 | Paper |
| A replacement for Voronoi diagrams of near linear size | 2026-05-08 | Paper |
| Taking a walk in a planar arrangement | 2026-05-06 | Paper |
| On undecided LP, clustering and active learning | 2026-04-27 | Paper |
| Stabbing convex bodies with lines and flats | 2026-04-27 | Paper |
| Reliable spanners for metric spaces | 2026-04-27 | Paper |
| Active learning a convex body in low dimensions | 2026-03-18 | Paper |
| Oracle-augmented prophet inequalities | 2026-01-14 | Paper |
| No-dimensional Tverberg partitions revisited | 2025-12-02 | Paper |
| Local spanners revisited | 2025-12-02 | Paper |
| Near optimal locality sensitive orderings in Euclidean space | 2025-11-24 | Paper |
On the budgeted Hausdorff distance problem
CGT. Computing in Geometry and Topology | 2025-10-21 | Paper |
How packed is it, really?
CGT. Computing in Geometry and Topology | 2025-10-21 | Paper |
Near-optimal Euclidean locality-sensitive orderings
Journal of Computational Geometry | 2025-08-28 | Paper |
| Approximating minimization diagrams and generalized proximity search | 2025-05-20 | Paper |
| Down the rabbit hole: robust proximity search and density estimation in sublinear space | 2025-05-05 | Paper |
Computing instance-optimal kernels in two dimensions
Discrete & Computational Geometry | 2025-03-19 | Paper |
On the number of incidences when avoiding an induced biclique in geometric settings
Discrete & Computational Geometry | 2025-02-19 | Paper |
Sparsifying disk intersection graphs for reliable connectivity
CGT. Computing in Geometry and Topology | 2025-02-03 | Paper |
| Fast approximation algorithms for piercing boxes by points | 2024-11-28 | Paper |
| Computing instance-optimal kernels in two dimensions | 2024-10-16 | Paper |
| Revisiting random points: combinatorial complexity and algorithms | 2024-05-29 | Paper |
| Halving by a thousand cuts or punctures | 2024-05-14 | Paper |
| On the number of incidences when avoiding an induced biclique in geometric settings | 2024-05-14 | Paper |
| Approximation algorithms for maximum matchings in geometric intersection graphs | 2024-05-14 | Paper |
Fast Algorithms for Geometric Consensuses
(available as arXiv preprint) | 2023-11-02 | Paper |
Submodular clustering in low dimensions
(available as arXiv preprint) | 2023-11-02 | Paper |
Reliable Spanners for Metric Spaces
ACM Transactions on Algorithms | 2023-10-23 | Paper |
Improved Approximation Algorithms for Tverberg Partitions
(available as arXiv preprint) | 2023-09-20 | Paper |
A note on stabbing convex bodies with points, lines, and flats
Discrete & Computational Geometry | 2023-05-12 | Paper |
Edge Estimation with Independent Set Oracles
ACM Transactions on Algorithms | 2023-04-26 | Paper |
Few cuts meet many point sets
Algorithmica | 2023-04-11 | Paper |
| Sometimes Reliable Spanners of Almost Linear Size. | 2023-02-07 | Paper |
| scientific article; zbMATH DE number 7561404 (Why is no real title available?) | 2022-07-21 | Paper |
| On Locality-Sensitive Orderings and Their Applications | 2022-07-18 | Paper |
| Smallest k-enclosing rectangle revisited | 2022-07-18 | Paper |
| Journey to the Center of the Point Set | 2022-07-18 | Paper |
| A spanner for the day after | 2022-07-18 | Paper |
Optimal algorithms for geometric centers and depth
SIAM Journal on Computing | 2022-06-08 | Paper |
Sometimes reliable spanners of almost linear size
(available as arXiv preprint) | 2022-05-18 | Paper |
The maximum-level vertex in an arrangement of lines
Discrete & Computational Geometry | 2022-03-21 | Paper |
Journey to the Center of the Point Set
ACM Transactions on Algorithms | 2022-02-08 | Paper |
Smallest \(k\)-enclosing rectangle revisited
Discrete & Computational Geometry | 2021-08-18 | Paper |
Approximate sparse linear regression
(available as arXiv preprint) | 2021-07-28 | Paper |
Edge estimation with independent set oracles
(available as arXiv preprint) | 2021-06-15 | Paper |
Stabbing pairwise intersecting disks by five points
Discrete Mathematics | 2021-06-14 | Paper |
Stabbing pairwise intersecting disks by five points
Discrete Mathematics | 2021-06-14 | Paper |
Active-learning a convex body in low dimensions
Algorithmica | 2021-06-11 | Paper |
Grid Peeling and the Affine Curve-Shortening Flow
Experimental Mathematics | 2021-04-01 | Paper |
Fast LP-based Approximations for Geometric Packing and Covering Problems
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
A spanner for the day after
Discrete & Computational Geometry | 2021-01-29 | Paper |
Approximate greedy clustering and distance selection for graph metrics
(available as arXiv preprint) | 2021-01-12 | Paper |
On locality-sensitive orderings and their applications
SIAM Journal on Computing | 2020-08-03 | Paper |
Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
Discrete & Computational Geometry | 2020-06-16 | Paper |
On separating points by lines
Discrete & Computational Geometry | 2020-04-07 | Paper |
Approximation schemes for independent set and sparse subsets of polygons
Journal of the ACM | 2020-02-11 | Paper |
Sparse Approximation via Generating Point Sets
ACM Transactions on Algorithms | 2019-11-25 | Paper |
Grid peeling and the affine curve-shortening flow
2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX) | 2019-09-12 | Paper |
Euclidean spanners in high dimensions
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Jaywalking your dog: computing the Fréchet distance with shortcuts | 2019-05-10 | Paper |
The one-round Voronoi game
Proceedings of the eighteenth annual symposium on Computational geometry | 2018-11-23 | Paper |
Projective clustering in high dimensions using core-sets
Proceedings of the eighteenth annual symposium on Computational geometry | 2018-11-23 | Paper |
Optimally cutting a surface into a disk
Proceedings of the eighteenth annual symposium on Computational geometry | 2018-11-23 | Paper |
Nearest-neighbor searching under uncertainty. II
ACM Transactions on Algorithms | 2018-11-05 | Paper |
On the expected complexity of Voronoi diagrams on terrains
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Net and prune: a linear time algorithm for Euclidean distance problems
Journal of the ACM | 2018-08-02 | Paper |
Proximity in the age of distraction: robust approximate nearest neighbor search
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Sparse approximation via generating point sets
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Approximating the k-level in three-dimensional plane arrangements
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
On the Complexity of Randomly Weighted Voronoi Diagrams
Proceedings of the thirtieth annual symposium on Computational geometry | 2018-04-23 | Paper |
Quasi-polynomial time approximation scheme for sparse subsets of polygons
Proceedings of the thirtieth annual symposium on Computational geometry | 2018-04-23 | Paper |
| scientific article; zbMATH DE number 6850368 (Why is no real title available?) | 2018-03-15 | Paper |
Robust proximity search for balls using sublinear space
Algorithmica | 2018-02-28 | Paper |
Robust proximity search for balls using sublinear space
Algorithmica | 2018-02-28 | Paper |
Approximating the k-Level in Three-Dimensional Plane Arrangements
A Journey Through Discrete Mathematics | 2018-02-26 | Paper |
Separating a Voronoi diagram via local search
(available as arXiv preprint) | 2018-01-30 | Paper |
Geometric Packing under Nonuniform Constraints
SIAM Journal on Computing | 2017-11-22 | Paper |
Approximation algorithms for polynomial-expansion and low-density graphs
SIAM Journal on Computing | 2017-11-22 | Paper |
Smaller coresets for \(k\)-median and \(k\)-means clustering
Proceedings of the twenty-first annual symposium on Computational geometry | 2017-10-20 | Paper |
Fast construction of nets in low dimensional metrics, and their applications
Proceedings of the twenty-first annual symposium on Computational geometry | 2017-10-20 | Paper |
A time-optimal delaunay refinement algorithm in two dimensions
Proceedings of the twenty-first annual symposium on Computational geometry | 2017-10-20 | Paper |
Approximation algorithms for maximum independent set of pseudo-disks
Proceedings of the twenty-fifth annual symposium on Computational geometry | 2017-10-20 | Paper |
On the set multi-cover problem in geometric settings
Proceedings of the twenty-fifth annual symposium on Computational geometry | 2017-10-20 | Paper |
| Space exploration via proximity search | 2017-10-10 | Paper |
| From proximity to utility: a Voronoi partition of Pareto optima | 2017-10-10 | Paper |
| Shortest Path in a Polygon using Sublinear Space. | 2017-10-10 | Paper |
Convex hulls under uncertainty
Algorithmica | 2017-10-10 | Paper |
A practical approach for computing the diameter of a point set
Proceedings of the seventeenth annual symposium on Computational geometry | 2017-09-29 | Paper |
On conflict-free coloring of points and simple regions in the plane
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
Hausdorff distance under translation for points and balls
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
Computing approximate shortest paths on convex polytopes
Proceedings of the sixteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
Shape fitting with outliers
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
On the least median square problem
Proceedings of the twentieth annual symposium on Computational geometry | 2017-09-29 | Paper |
Efficient algorithms for shared camera control
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
High-dimensional shape fitting in linear time
Proceedings of the nineteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
When crossings count — approximating the minimum spanning tree
Proceedings of the sixteenth annual symposium on Computational geometry | 2017-09-29 | Paper |
| scientific article; zbMATH DE number 6783438 (Why is no real title available?) | 2017-09-29 | Paper |
Approximating the maximum overlap of polygons under translation
Algorithmica | 2017-05-11 | Paper |
| Robust proximity search for balls using sublinear space | 2017-04-25 | Paper |
Shortest path in a polygon using sublinear space
(available as arXiv preprint) | 2017-03-30 | Paper |
| Weighted geometric set cover problems revisited | 2017-03-09 | Paper |
| Minimum convex partitions and maximum empty polytopes | 2017-03-09 | Paper |
From proximity to utility: a Voronoi partition of Pareto optima
Discrete & Computational Geometry | 2016-10-27 | Paper |
From proximity to utility: a Voronoi partition of Pareto optima
Discrete & Computational Geometry | 2016-10-27 | Paper |
Space exploration via proximity search
Discrete & Computational Geometry | 2016-09-14 | Paper |
Space exploration via proximity search
Discrete & Computational Geometry | 2016-09-14 | Paper |
How to walk your dog in the mountains with no magic leash
Discrete & Computational Geometry | 2016-02-29 | Paper |
On the number of edges of fan-crossing free graphs
Algorithmica | 2016-02-19 | Paper |
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
Algorithms - ESA 2015 | 2015-11-19 | Paper |
Approximating Minimization Diagrams and Generalized Proximity Search
SIAM Journal on Computing | 2015-08-18 | Paper |
The Fréchet distance revisited and extended
ACM Transactions on Algorithms | 2015-08-14 | Paper |
| scientific article; zbMATH DE number 6469255 (Why is no real title available?) | 2015-08-03 | Paper |
On the complexity of randomly weighted multiplicative Voronoi diagrams
Discrete & Computational Geometry | 2015-06-18 | Paper |
On the set multicover problem in geometric settings
ACM Transactions on Algorithms | 2014-12-05 | Paper |
Hausdorff distance under translation for points and balls
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Union of random Minkowski sums and network vulnerability analysis
Discrete & Computational Geometry | 2014-11-14 | Paper |
Down the rabbit hole: robust proximity search and density estimation in sublinear space
SIAM Journal on Computing | 2014-11-14 | Paper |
| How fast is the \(k\)-means method? | 2014-10-13 | Paper |
| On approximating the depth and related problems | 2014-10-13 | Paper |
Approximating the maximum overlap of polygons under translation
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Convex hulls under uncertainty
Lecture Notes in Computer Science | 2014-10-08 | Paper |
How to walk your dog in the mountains with no magic leash
1293.6829 | 2014-08-07 | Paper |
Net and prune: a linear time algorithm for Euclidean distance problems
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
Geometric packing under non-uniform constraints
Proceedings of the twenty-eighth annual symposium on Computational geometry | 2014-08-07 | Paper |
On the expected complexity of Voronoi diagrams on terrains
Proceedings of the twenty-eighth annual symposium on Computational geometry | 2014-08-07 | Paper |
Approximating the Fréchet distance for realistic curves in near linear time
Proceedings of the twenty-sixth annual symposium on Computational geometry | 2014-04-03 | Paper |
New constructions of SSPDs and their applications
Proceedings of the twenty-sixth annual symposium on Computational geometry | 2014-04-03 | Paper |
The frechet distance revisited and extended
Proceedings of the twenty-seventh annual symposium on Computational geometry | 2014-03-24 | Paper |
Jaywalking your dog: computing the Fréchet distance with shortcuts
SIAM Journal on Computing | 2014-02-04 | Paper |
On the number of edges of fan-crossing free graphs
Lecture Notes in Computer Science | 2014-01-14 | Paper |
Peeling the grid
SIAM Journal on Discrete Mathematics | 2013-09-26 | Paper |
Embeddings of surfaces, curves, and moving points in Euclidean space
SIAM Journal on Computing | 2013-07-24 | Paper |
Approximate nearest neighbor search for low-dimensional queries
SIAM Journal on Computing | 2013-07-04 | Paper |
Approximate nearest neighbor: towards removing the curse of dimensionality
Theory of Computing | 2012-09-27 | Paper |
Approximation algorithms for maximum independent set of pseudo-disks
Discrete & Computational Geometry | 2012-09-19 | Paper |
Minimum Convex Partitions and Maximum Empty Polytopes
Algorithm Theory – SWAT 2012 | 2012-08-14 | Paper |
Approximating the Fréchet distance for realistic curves in near linear time
Discrete & Computational Geometry | 2012-08-13 | Paper |
New constructions of SSPDs and their applications
Computational Geometry | 2012-05-18 | Paper |
| Generalization bounds for the area under the ROC curve | 2011-10-12 | Paper |
Computing the Fréchet distance between folded polygons
Lecture Notes in Computer Science | 2011-08-12 | Paper |
| Geometric approximation algorithms | 2011-07-04 | Paper |
Relative (p, )-approximations in geometry
Discrete & Computational Geometry | 2011-03-31 | Paper |
Approximating extent measures of points.
Journal of the ACM | 2011-02-01 | Paper |
Robust shape fitting via peeling and grating coresets
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
On coresets for k-means and k-median clustering
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Approximate clustering via core-sets
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Algorithms - ESA 2003
Lecture Notes in Computer Science | 2010-03-03 | Paper |
Guarding galleries and terrains
Information Processing Letters | 2010-01-29 | Paper |
Covering many or few points with unit disks
Theory of Computing Systems | 2009-09-02 | Paper |
On Approximating the Depth and Related Problems
SIAM Journal on Computing | 2009-06-22 | Paper |
| Robust shape fitting via peeling and grating coresets | 2009-04-14 | Paper |
The Euclidean Orienteering Problem Revisited
SIAM Journal on Computing | 2009-03-16 | Paper |
Embeddings of surfaces, curves, and moving points in euclidean space
Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 | 2009-02-12 | Paper |
On approximate halfspace range counting and relative epsilon-approximations
Proceedings of the twenty-third annual symposium on Computational geometry - SCG '07 | 2009-02-12 | Paper |
| scientific article; zbMATH DE number 5506214 (Why is no real title available?) | 2009-02-10 | Paper |
| scientific article; zbMATH DE number 5506232 (Why is no real title available?) | 2009-02-10 | Paper |
Coresets for Discrete Integration and Clustering
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science | 2008-04-17 | Paper |
Robust shape fitting via peeling and grating coresets
Discrete & Computational Geometry | 2008-04-16 | Paper |
Fréchet Distance for Curves, Revisited
Lecture Notes in Computer Science | 2008-03-11 | Paper |
Covering Many or Few Points with Unit Disks
Approximation and Online Algorithms | 2008-02-21 | Paper |
Finding a guard that sees most and a shop that sells most
Discrete & Computational Geometry | 2007-06-21 | Paper |
How to get close to the median shape
Computational Geometry | 2007-03-12 | Paper |
Smaller coresets for k-median and k-means clustering
Discrete & Computational Geometry | 2007-02-14 | Paper |
On the least median square problem
Discrete & Computational Geometry | 2006-12-06 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
SIAM Journal on Computing | 2006-06-01 | Paper |
| scientific article; zbMATH DE number 5019895 (Why is no real title available?) | 2006-04-28 | Paper |
Near-linear time approximation algorithms for curve simplification
Algorithmica | 2006-03-21 | Paper |
On the Fermat-Weber center of a convex object
Computational Geometry | 2005-11-01 | Paper |
Approximating \(k\)-hop minimum-spanning trees
Operations Research Letters | 2005-08-25 | Paper |
Conflict-free coloring of points and simple regions in the plane
Discrete & Computational Geometry | 2005-08-17 | Paper |
FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
Lecture Notes in Computer Science | 2005-08-12 | Paper |
POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
International Journal of Computational Geometry & Applications | 2005-06-10 | Paper |
Geographic quorum system approximations
Algorithmica | 2005-04-29 | Paper |
AN EXPERIMENTAL STUDY OF ON-LINE METHODS FOR ZONE CONSTRUCTION IN ARRANGEMENTS OF LINES IN THE PLANE
International Journal of Computational Geometry & Applications | 2005-03-30 | Paper |
Fast algorithms for computing the smallest \(k\)-enclosing circle
Algorithmica | 2005-02-21 | Paper |
How fast is the \(k\)-means method?
Algorithmica | 2005-02-21 | Paper |
Shape Fitting with Outliers
SIAM Journal on Computing | 2005-02-21 | Paper |
High-dimensional shape fitting in linear time
Discrete & Computational Geometry | 2005-02-11 | Paper |
Clustering motion
Discrete & Computational Geometry | 2004-12-13 | Paper |
The one-round Voronoi game
Discrete & Computational Geometry | 2004-03-11 | Paper |
Optimally cutting a surface into a disk
Discrete & Computational Geometry | 2004-03-11 | Paper |
| scientific article; zbMATH DE number 1966629 (Why is no real title available?) | 2003-08-18 | Paper |
| scientific article; zbMATH DE number 1947379 (Why is no real title available?) | 2003-07-08 | Paper |
| scientific article; zbMATH DE number 1926669 (Why is no real title available?) | 2003-06-11 | Paper |
New similarity measures between polylines with applications to morphing and polygon sweeping
Discrete & Computational Geometry | 2003-03-17 | Paper |
Reporting intersecting pairs of convex polytopes in two and three dimensions
Computational Geometry | 2003-03-10 | Paper |
| scientific article; zbMATH DE number 1830727 (Why is no real title available?) | 2002-11-18 | Paper |
| Morphing between polylines | 2002-07-16 | Paper |
Computing approximate shortest paths on convex polytopes
Algorithmica | 2002-06-17 | Paper |
| Maintaining approximate extent measures of moving points | 2002-03-24 | Paper |
| Online point location in planar arrangements and its applications | 2002-01-30 | Paper |
Penetration depth of two convex polytopes in 3D
Nordic Journal of Computing | 2002-01-17 | Paper |
Online point location in planar arrangements and its applications
Discrete & Computational Geometry | 2002-01-17 | Paper |
Approximation algorithms for minimum-width annuli and shells
Discrete & Computational Geometry | 2001-08-16 | Paper |
| scientific article; zbMATH DE number 1617270 (Why is no real title available?) | 2001-07-11 | Paper |
Efficiently approximating the minimum-volume bounding box of a point set in three dimensions
Journal of Algorithms | 2001-04-17 | Paper |
Taking a walk in a planar arrangement
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1445396 (Why is no real title available?) | 2001-01-29 | Paper |
Constructing Planar Cuttings in Theory and Practice
SIAM Journal on Computing | 2000-10-18 | Paper |
Multicolor combination lemma
Computational Geometry | 2000-10-17 | Paper |
| scientific article; zbMATH DE number 1305395 (Why is no real title available?) | 2000-02-02 | Paper |
Constructing Approximate Shortest Path Maps in Three Dimensions
SIAM Journal on Computing | 1999-10-28 | Paper |
Approximate shortest paths and geodesic diameter on a convex polytope in three dimensions
Discrete & Computational Geometry | 1999-09-30 | Paper |
| scientific article; zbMATH DE number 1305490 (Why is no real title available?) | 1999-06-17 | Paper |
An output sensitive algorithm for discrete convex hulls
Computational Geometry | 1998-06-08 | Paper |
Approximating shortest paths on a convex polytope in three dimensions
Journal of the ACM | 1998-02-17 | Paper |
