2024
Revisiting Random Points: Combinatorial Complexity and Algorithms.
Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024
Fast Approximation Algorithms for Piercing Boxes by Points.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
2023
A Note on Stabbing Convex Bodies with Points, Lines, and Flats.
Discret. Comput. Geom., June, 2023
Few Cuts Meet Many Point Sets.
Algorithmica, April, 2023
Reliable Spanners for Metric Spaces.
ACM Trans. Algorithms, January, 2023
On the Rectangles Induced by Points.
CoRR, 2023
Almost Optimal Locality Sensitive Orderings in Euclidean Space.
CoRR, 2023
Approximately: Independence Implies Vertex Cover.
CoRR, 2023
On the Budgeted Hausdorff Distance Problem.
CoRR, 2023
No-dimensional Tverberg Partitions Revisited.
CoRR, 2023
On the Width of the Regular n-Simplex.
CoRR, 2023
Halving by a Thousand Cuts or Punctures.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023
Computing Instance-Optimal Kernels in Two Dimensions.
Proceedings of the 39th International Symposium on Computational Geometry, 2023
2022
Sampling a Near Neighbor in High Dimensions - Who is the Fairest of Them All?
ACM Trans. Database Syst., 2022
Optimal Algorithms for Geometric Centers and Depth.
SIAM J. Comput., 2022
Sometimes reliable spanners of almost linear size.
J. Comput. Geom., 2022
The Maximum-Level Vertex in an Arrangement of Lines.
Discret. Comput. Geom., 2022
Computing Optimal Kernels in Two Dimensions.
CoRR, 2022
Sparsifying Disk Intersection Graphs for Reliable Connectivity.
CoRR, 2022
Local Spanners Revisited.
CoRR, 2022
Sampling near neighbors in search for fairness.
Commun. ACM, 2022
Approximation Algorithms for Maximum Matchings in Geometric Intersection Graphs.
Proceedings of the 38th International Symposium on Computational Geometry, 2022
2021
Journey to the Center of the Point Set.
ACM Trans. Algorithms, 2021
Fair near neighbor search via sampling.
SIGMOD Rec., 2021
Stabbing pairwise intersecting disks by five points.
Discret. Math., 2021
Smallest k-Enclosing Rectangle Revisited.
Discret. Comput. Geom., 2021
On the Number of Incidences when Avoiding the Klan.
CoRR, 2021
On Competitive Permutations for Set Cover by Intervals.
CoRR, 2021
On Clusters that are Separated but Large.
CoRR, 2021
How Packed Is It, Really?
CoRR, 2021
Active-Learning a Convex Body in Low Dimensions.
Algorithmica, 2021
Improved Approximation Algorithms for Tverberg Partitions.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021
Stabbing Convex Bodies with Lines and Flats.
Proceedings of the 37th International Symposium on Computational Geometry, 2021
On Undecided LP, Clustering and Active Learning.
Proceedings of the 37th International Symposium on Computational Geometry, 2021
2020
Edge Estimation with Independent Set Oracles.
ACM Trans. Algorithms, 2020
On Locality-Sensitive Orderings and Their Applications.
SIAM J. Comput., 2020
Approximate greedy clustering and distance selection for graph metrics.
J. Comput. Geom., 2020
Grid Peeling and the Affine Curve-Shortening Flow.
Exp. Math., 2020
On Separating Points by Lines.
Discret. Comput. Geom., 2020
Decomposing Arrangements of Hyperplanes: VC-Dimension, Combinatorial Dimension, and Point Location.
Discret. Comput. Geom., 2020
A Spanner for the Day After.
Discret. Comput. Geom., 2020
Shortest Secure Path in a Voronoi Diagram.
CoRR, 2020
Reliable Spanners for Metric Spaces.
CoRR, 2020
Submodular Clustering in Low Dimensions.
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020
Fast LP-based Approximations for Geometric Packing and Covering Problems.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020
Fast Algorithms for Geometric Consensuses.
Proceedings of the 36th International Symposium on Computational Geometry, 2020
Some Geometric Applications of Anti-Chains.
Proceedings of the 32nd Canadian Conference on Computational Geometry, 2020
2019
Sparse Approximation via Generating Point Sets.
ACM Trans. Algorithms, 2019
Approximation Schemes for Independent Set and Sparse Subsets of Polygons.
J. ACM, 2019
Covering Polygons by Min-Area Convex Polygons.
CoRR, 2019
Proof of Dudley's Convex Approximation.
CoRR, 2019
Near Neighbor: Who is the Fairest of Them All?
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019
2018
Coresets for $k$-Means and $k$-Median Clustering and their Applications.
CoRR, 2018
Two (Known) Results About Graphs with No Short Odd Cycles.
CoRR, 2018
Separators for Planar Graphs that are Almost Trees.
CoRR, 2018
Robust Proximity Search for Balls Using Sublinear Space.
Algorithmica, 2018
Approximate Sparse Linear Regression.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018
2017
Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs.
SIAM J. Comput., 2017
Geometric Packing under Nonuniform Constraints.
SIAM J. Comput., 2017
How to Net a Convex Shape.
CoRR, 2017
A Simple Algorithm for Computing a Cycle Separator.
CoRR, 2017
LSH on the Hypercube Revisited.
CoRR, 2017
Approximating the Maximum Overlap of Polygons under Translation.
Algorithmica, 2017
Convex Hulls Under Uncertainty.
Algorithmica, 2017
Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017
2016
On the Expected Complexity of Voronoi Diagrams on Terrains.
ACM Trans. Algorithms, 2016
Nearest-Neighbor Searching Under Uncertainty II.
ACM Trans. Algorithms, 2016
Shortest path in a polygon using sublinear space.
J. Comput. Geom., 2016
How to Walk Your Dog in the Mountains with No Magic Leash.
Discret. Comput. Geom., 2016
Space Exploration via Proximity Search.
Discret. Comput. Geom., 2016
From Proximity to Utility: A Voronoi Partition of Pareto Optima.
Discret. Comput. Geom., 2016
Notes on Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs.
CoRR, 2016
Approximating the $k$-Level in Three-Dimensional Plane Arrangements.
CoRR, 2016
Computing the k Nearest-Neighbors for all Vertices via Dijkstra.
CoRR, 2016
Approximating the <i>k</i>-Level in Three-Dimensional Plane Arrangements.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016
Towards Tight Bounds for the Streaming Set Cover Problem.
Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2016
Separating a Voronoi Diagram via Local Search.
Proceedings of the 32nd International Symposium on Computational Geometry, 2016
2015
Approximating Minimization Diagrams and Generalized Proximity Search.
SIAM J. Comput., 2015
Net and Prune: A Linear Time Algorithm for Euclidean Distance Problems.
J. ACM, 2015
On the Complexity of Randomly Weighted Multiplicative Voronoi Diagrams.
Discret. Comput. Geom., 2015
Approximation Algorithms for Low-Density Graphs.
CoRR, 2015
A Simple Algorithm for Maximum Margin Classification, Revisited.
CoRR, 2015
On the Number of Edges of Fan-Crossing Free Graphs.
Algorithmica, 2015
2014
The fréchet distance revisited and extended.
ACM Trans. Algorithms, 2014
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space.
SIAM J. Comput., 2014
Minimum Convex Partitions and Maximum Empty Polytopes.
J. Comput. Geom., 2014
Union of Random Minkowski Sums and Network Vulnerability Analysis.
Discret. Comput. Geom., 2014
Epsilon-Nets for Halfspaces Revisited.
CoRR, 2014
Low Rank Matrix Approximation in Linear Time.
CoRR, 2014
Separating a Voronoi Diagram.
CoRR, 2014
On the Complexity of Randomly Weighted Voronoi Diagrams.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014
Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons.
Proceedings of the 30th Annual Symposium on Computational Geometry, 2014
2013
SIAM J. Discret. Math., 2013
Approximate Nearest Neighbor Search for Low-Dimensional Queries.
SIAM J. Comput., 2013
Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts.
SIAM J. Comput., 2013
Embeddings of Surfaces, Curves, and Moving Points in Euclidean Space.
SIAM J. Comput., 2013
Fast Clustering with Lower Bounds: No Customer too Far, No Shop too Small
CoRR, 2013
Euclidean spanners in high dimensions.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013
2012
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality.
Theory Comput., 2012
On the set multicover problem in geometric settings.
ACM Trans. Algorithms, 2012
Weighted geometric set cover problems revisited.
J. Comput. Geom., 2012
Approximating the Fréchet Distance for Realistic Curves in Near Linear Time.
Discret. Comput. Geom., 2012
Approximation Algorithms for Maximum Independent Set of Pseudo-Disks.
Discret. Comput. Geom., 2012
Faster Approximate Distance Queries and Compact Routing in Sparse Graphs
CoRR, 2012
New constructions of SSPDs and their applications.
Comput. Geom., 2012
Geometric packing under non-uniform constraints.
Proceedings of the 28th ACM Symposium on Computational Geometry, 2012
2011
Relative (<i>p</i>, <i>ε</i>)-Approximations in Geometry.
Discret. Comput. Geom., 2011
On the Expected Complexity of Random Convex Hulls
CoRR, 2011
Down the Rabbit Hole: Robust Proximity Search in Sublinear Space
CoRR, 2011
A Simple Proof of the Existence of a Planar Separator
CoRR, 2011
Computing the Fréchet Distance between Folded Polygons.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011
Approximate distance queries and compact routing in sparse graphs.
Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011
2010
Hausdorff distance under translation for points and balls.
ACM Trans. Algorithms, 2010
2009
Covering Many or Few Points with Unit Disks.
Theory Comput. Syst., 2009
Relative (p,epsilon)-Approximations in Geometry
CoRR, 2009
Carnival of Samplings: Nets, Approximations, Relative and Sensitive
CoRR, 2009
Being Fat and Friendly is Not Enough
CoRR, 2009
Approximating Spanning Trees with Low Crossing Number
CoRR, 2009
Randomized Incremental Construction of Compressed Quadtrees
CoRR, 2009
Hierarchical neighbor graphs: A low stretch connected structure for points in Euclidean space
CoRR, 2009
On the set multi-cover problem in geometric settings.
Proceedings of the 25th ACM Symposium on Computational Geometry, 2009
2008
The Euclidean Orienteering Problem Revisited.
SIAM J. Comput., 2008
On Approximating the Depth and Related Problems.
SIAM J. Comput., 2008
Robust Shape Fitting via Peeling and Grating Coresets.
Discret. Comput. Geom., 2008
Proceedings of the Algorithms, 2008
2007
Smaller Coresets for k-Median and k-Means Clustering.
Discret. Comput. Geom., 2007
Finding a Guard that Sees Most and a Shop that Sells Most.
Discret. Comput. Geom., 2007
How to get close to the median shape.
Comput. Geom., 2007
Maximum Margin Coresets for Active and Noise Tolerant Learning.
Proceedings of the IJCAI 2007, 2007
On approximate halfspace range counting and relative epsilon-approximations.
Proceedings of the 23rd ACM Symposium on Computational Geometry, 2007
2006
Fast Construction of Nets in Low-Dimensional Metrics and Their Applications.
SIAM J. Comput., 2006
Guarding galleries and terrains.
Inf. Process. Lett., 2006
On the Least Median Square Problem.
Discret. Comput. Geom., 2006
Coresets for Discrete Integration and Clustering.
Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006
Fréchet Distance for Curves, Revisited.
Proceedings of the Algorithms, 2006
The orienteering problem in the plane revisited.
Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006
2005
Approximating <i>k</i>-hop minimum-spanning trees.
Oper. Res. Lett., 2005
Generalization Bounds for the Area Under the ROC Curve.
J. Mach. Learn. Res., 2005
Conflict-Free Coloring of Points and Simple Regions in the Plane.
Discret. Comput. Geom., 2005
On the Fermat-Weber center of a convex object.
Comput. Geom., 2005
How Fast Is the k-Means Method?
Algorithmica, 2005
Fast Algorithms for Computing the Smallest k-Enclosing Circle.
Algorithmica, 2005
Geographic Quorum System Approximations.
Algorithmica, 2005
Near-Linear Time Approximation Algorithms for Curve Simplification.
Algorithmica, 2005
Separability with Outliers.
Proceedings of the Algorithms and Computation, 16th International Symposium, 2005
Approximation algorithm for the L1-fitting circle problem.
Proceedings of the (Informal) Proceedings of the 21st European Workshop on Computational Geometry, 2005
A time-optimal delaunay refinement algorithm in two dimensions.
Proceedings of the 21st ACM Symposium on Computational Geometry, 2005
Dynamic Well-Separated Pair Decomposition Made Easy.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
Staying in the Middle: Exact and Approximate Medians in R1 and R2 for Moving Points.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005
Approximation algorithms for location problems in sensor networks.
Proceedings of the 2nd International Conference on Broadband Networks (BROADNETS 2005), 2005
A Uniform Convergence Bound for the Area Under the ROC Curve.
Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics, 2005
2004
Shape Fitting with Outliers.
SIAM J. Comput., 2004
Approximating extent measures of points.
J. ACM, 2004
High-Dimensional Shape Fitting in Linear Time.
Discret. Comput. Geom., 2004
Discret. Comput. Geom., 2004
Optimally Cutting a Surface into a Disk.
Discret. Comput. Geom., 2004
The One-Round Voronoi Game.
Discret. Comput. Geom., 2004
On coresets for k-means and k-median clustering.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004
Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004
2003
An Experimental Study of On-Line Methods for Zone Construction in Arrangements of Lines in the Plane.
Int. J. Comput. Geom. Appl., 2003
Fast Algorithms for Computing the Smallest k-Enclosing Disc.
Proceedings of the Algorithms, 2003
Efficient algorithms for shared camera control.
Proceedings of the 19th ACM Symposium on Computational Geometry, 2003
2002
New Similarity Measures between Polylines with Applications to Morphing and Polygon Sweeping.
Discret. Comput. Geom., 2002
Algorithmic issues in modeling motion.
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
ACM Comput. Surv., 2002
Reporting intersecting pairs of convex polytopes in two and three dimensions.
Comput. Geom., 2002
Computing Approximate Shortest Paths on Convex Polytopes.
Algorithmica, 2002
Approximate clustering via core-sets.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002
Constraint Classification for Multiclass Classification and Ranking.
Proceedings of the Advances in Neural Information Processing Systems 15 [Neural Information Processing Systems, 2002
On generalization bounds, projection profile, and margin distribution.
Proceedings of the Machine Learning, 2002
Projective clustering in high dimensions using core-sets.
Proceedings of the 18th Annual Symposium on Computational Geometry, 2002
Constraint Classification: A New Approach to Multiclass Classification.
Proceedings of the Algorithmic Learning Theory, 13th International Conference, 2002
STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects.
Proceedings of the Algorithm Engineering and Experiments, 4th International Workshop, 2002
2001
IEEE/ACM Trans. Netw., 2001
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions.
J. Algorithms, 2001
Polygon Containment and Translational Min-Hausdorff-Distance Between Segment Sets are 3SUM-Hard.
Int. J. Comput. Geom. Appl., 2001
Online Point Location in Planar Arrangements and Its Applications.
Discret. Comput. Geom., 2001
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001
Morphing between polylines.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
Maintaining approximate extent measures of moving points.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
Approximate Shape Fitting via Linearization.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
A Replacement for Voronoi Diagrams of Near Linear Size.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001
An On-line Occlusio-Culling Algorithm for FastWalkthrough in Urban Areas.
Proceedings of the 22nd Annual Conference of the European Association for Computer Graphics, 2001
A practical approach for computing the diameter of a point set.
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, 2001
2000
Taking a Walk in a Planar Arrangement.
SIAM J. Comput., 2000
Constructing Planar Cuttings in Theory and Practice.
SIAM J. Comput., 2000
Penetration Depth of Two Convex Polytopes in 3D.
Nord. J. Comput., 2000
Approximation Algorithms for Minimum-Width Annuli and Shells.
Discret. Comput. Geom., 2000
Computing the Penetration Depth of Two Convex Polytopes in 3D.
Proceedings of the Algorithm Theory, 2000
Sweeping simple polygons with a chain of guards.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000
When crossings count - approximating the minimum spanning tree.
Proceedings of the Sixteenth Annual Symposium on Computational Geometry, 2000
1999
Constructing Approximate Shortest Path Maps in Three Dimensions.
SIAM J. Comput., 1999
Approximate Shortest Paths and Geodesic Diameter on a Convex Polytope in Three Dimensions.
Discret. Comput. Geom., 1999
Multicolor Combination Lemma.
Comput. Geom., 1999
On-Line Zone Construction in Arrangements of Lines in the Plane.
Proceedings of the Algorithm Engineering, 1999
Approximation and Exact Algorithms for Minimum-Width Annuli and Shells.
Proceedings of the Fifteenth Annual Symposium on Computational Geometry, 1999
1998
An output sensitive algorithm for discrete convex hulls.
Comput. Geom., 1998
Constructing Cuttings in Theory and Practice.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998
Fly Cheaply: On the Minimum Fuel-Consumption Problem.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998
Results on <i>k</i>-Sets and <i>j</i>-Facets via Continuous Motion.
Proceedings of the Fourteenth Annual Symposium on Computational Geometry, 1998
1997
Approximating shortest paths on a convex polytope in three dimensions.
J. ACM, 1997
Approximate Shortest Paths and Geodesic Diameters on Convex Polytopes in Three Dimensions.
Proceedings of the Thirteenth Annual Symposium on Computational Geometry, 1997
1996
Approximating Shortest Paths on a Convex Polytope in Three Dimensions.
Proceedings of the Twelfth Annual Symposium on Computational Geometry, 1996
1995
The complexity of a single face of a minkowski sum.
Proceedings of the 7th Canadian Conference on Computational Geometry, 1995
