Sariel Har-Peled

Orcid: 0000-0003-2638-9635

Affiliations:
  • University of Illinois at Urbana-Champaign, IL, USA


According to our database1, Sariel Har-Peled authored at least 210 papers between 1995 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
The Fréchet Distance Unleashed: Approximating a Dog with a Frog.
CoRR, 2024

Dependable Spanners via Unreliable Edges.
CoRR, 2024

SPITE: Simple Polyhedral Intersection Techniques for modified Environments.
CoRR, 2024

Approximating Densest Subgraph in Geometric Intersection Graphs.
CoRR, 2024

No-Dimensional Tverberg Partitions Revisited.
Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 2024

Local Spanners Revisited.
Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory, 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

Oracle-Augmented Prophet Inequalities.
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

Near Optimal Locality Sensitive Orderings in Euclidean Space.
Proceedings of the 40th International Symposium on Computational Geometry, 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 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

On the Budgeted Hausdorff Distance Problem.
Proceedings of the 35th Canadian Conference 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

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
Peeling the Grid.
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

Range Medians.
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

Clustering Motion.
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

No, Coreset, No Cry.
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
Routing with a clue.
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


  Loading...