Relative $(p,\epsilon)$-Approximations in Geometry (2009)
Har-Peled, Sariel, Sharir, Micha
We re-examine the notion of relative $(p,\eps)$-approximations, recently introduced in [CKMS06], and establish upper bounds on their size, in general range spaces of finite VC-dimension, using the...
On the Set Multi-Cover Problem in Geometric Settings (2009)
Chekuri, Chandra, Clarkson, Kenneth L., Har-Peled, Sariel
We consider the set multi-cover problem in geometric settings. Given a set of points P and a collection of geometric shapes (or sets) F, we wish to find a minimum cardinality subset of F such that...
Carnival of Samplings: Nets, Approximations, Relative and Sensitive (2009)
We survey several results known on sampling in computational geometry.
Being Fat and Friendly is Not Enough (2009)
We show that there is no $(1+\eps)$-approximation algorithm for the problem of covering points in the plane by minimum number of fat triangles of similar size (with the minimum angle of the triangles...
Approximating Spanning Trees with Low Crossing Number (2009)
We present a linear programming based algorithm for computing a spanning tree $T$ of a set $P$ of $n$ points in $\Re^d$, such that its crossing number is $O(\min(t \log n, n^{1-1/d}))$, where $t$ the...
Randomized Incremental Construction of Compressed Quadtrees (2009)
We present a simple randomized incremental algorithm for building compressed quadtrees. The resulting algorithm seems to be simpler than previously known algorithms for this task.
There are n types of coupons, and at each trial one coupon is picked in random. How many trials one has to perform before picking all coupons? Let m be the number of trials performed. We would like...
Hierarchical neighbor graphs: A low stretch connected structure for points in Euclidean space (2009)
Bagchi, Amitabha, Har-Peled, Sariel, Premi, Achal, Madan, Adit
In this paper we introduce a new randomized method for constructing a bounded degree connected structure on points in Euclidean space: $p$-hierarchical neighbor graphs. These graphs are parametrized...
Sariel Har-peled, David Hilbert, Theorem Let X, Om Varaibles, Such That Pr[xi
2, for i = 1,..., n. Let Y = �n i=1 Xi. Then, for any ∆> 0, we have Pr[Y ≥ ∆] ≤ e −∆2 /2n. Proof: Clearly, for an arbitrary t, to specified shortly, we have Pr[Y ≥ ∆] =...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled
We introduce two new related metrics, the geodesic width and the link width, for measuring the “distance ” between two non-intersecting polylines in the plane. If the two polylines have n...
Two randomized incremental algorithms for planar arrangements, with a twist (2008)
Pankaj K. Agarwal, Sariel Har-Peled
We present two results related to randomized incremental construction of planar arrangements: • An algorithm for computing the union of triangles in the plane in a quasi output- sensitive time. •...
Computational Geometry Applications of Well Separted Pairs Decomposition (2008)
Based on results by Callahan and Kosaraju [CK95, CK93].
Abstract Efficient Algorithms for Shared Camera Control ∗ (2008)
Sariel Har-peled, Vladlen Koltun, Dezhen Song, Ken Goldberg
We consider a system that allows n networked users to share control over a robotic webcamera. Each user guides the camera pan, tilt and zoom, by drawing a rectangle in the user interface. The server...
General Terms Algorithms (2008)
Sariel Har-peled, N. Goodwin Avenue
In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in R d, which is of size independent of n. In particular, we construct a (k, ε)-coreset of...
Abstract Efficient Algorithms for Shared Camera Control ∗ (2008)
Sariel Har-peled, Vladlen Koltun, Dezhen Song, Ken Goldberg
We consider a system that allows n networked users to share control over a robotic webcamera. Each user draws a rectangle that specifies the camera pan, tilt, and zoom. The server adjusts the camera...
Har-Peled, Sariel, Muthukrishnan, S.
We study a generalization of the classical median finding problem to batched query case: given an array of unsorted $n$ items and $k$ (not necessarily disjoint) intervals in the array, the goal is to...
Sariel Har-peled, Bardia Sadri, Bardia Sadri, Sariel Har-peled
k-Median: min dist(p, C)
Ashutosh Garg, Sariel Har-peled, Dan Roth
On generalization bounds, projection profile, and margin
ABSTRACT On the Least Median Square Problem ∗ (2008)
Jeff Erickson, Sariel Har-peled
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
Shape fitting with outliers (2008)
Given a set H of n hyperplanes in IR d, we present an algorithm that ε-approximates the extent between the top and bottom k levels of the arrangement of H in time O(n+(k/ε) c), where c is a...
Approximating extent measures of points (2008)
Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan
We present a general technique for approximating various descriptors of the extent of a set P of n points in R d. For a given extent measure µ and a parameter ε> 0, it computes in time O(n +...
Gill Barequet, Sariel Har-peled
)-time algorithm for computing a (1 + ")-approximation of the minimum-volume bounding box of n points in IR 3. We also present a simpler algorithm whose running time is O(n log n +...
Occlusion Culling for Fast Walkthrough in Urban Areas (2007)
Pankaj K. Agarwal, Sariel Har-peled, Yusu Wang
Figure 1: Demonstration of our algorithm on a Manhattan-suburb city model with 27,400 polygons used in our walkthrough applications. (a) is a bird-eye view of the city model from some position. (b)...
Constructing Approximate Shortest Path Maps in Three Dimensions (2007)
We define two results on approximate shortest path maps in IR 3 . (i) Given a polyhedral surface or a convex polytope P with n edges in IR 3 , a source point s on P , and a real parameter 0 ! "...
Je Erickson, Sariel Har-peled, David M. Mount
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, T. M. Murali
We introduce two new related metrics, the geodesic width and the link width, for measuring the \distance " between two non-intersecting polylines in the plane. If the two polylines have n...
Geometric Shape Approximation via Linearization (2007)
Sariel Har-peled, Kasturi R. Varadarajan
Shape approximation is an important optimization problem in computational geometry. In this paper, we present a general technique for solving such problems. Given a point set P, this technique can be...
Sariel Har-peled, Shakhar Smorodinsky
In this paper, we study coloring problems related to frequency setting, the problems are of the following two types: CF-coloring of regions: Given a finite family
guidance, and numerous contributions to this work. (2007)
Sariel Har-peled, Prof Micha Sharir, Bernard Chazelle, Ken Clarkson, Alon Efrat, Jeff Erickson
by
Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir
Abstract. Let P = fP1; : : : ; Pmg be a set of m convex polytopes in R
Occlusion Culling for Fast Walkthrough in Urban Areas (2007)
Pankaj K. Agarwal, Sariel Har-peled, Yusu Wang
This paper describes a fast algorithm, based on occlusion culling, for rendering complex urban environments. Occlusion culling has been widely used to achieve interactive frame rates for rendering...
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions ⋆ (2007)
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold
Abstract. Let P = {P1,..., Pm} be a set of m convex polytopes in R d, for d = 2, 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i, j) such...
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2007)
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold
Let P = fP 1 ; : : : ; Pm g be a set of m convex polytopes in R d , for d = 2; 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i; j) such...
Approximation Algorithms for Minimum-Width Annuli and Shells (2007)
Pankaj K. Agarwal, Boris Aronov, Sariel Har-peled, Micha Sharir
The \roundness" of S can be measured by computing the width ! (S) of the thinnest spherical shell (or annulus in ) that contains S. This paper contains two main results related to computing :...
Occlusion Culling for Fast Walkthrough in Urban Areas (2007)
Yusu Wang Pankaj, Pankaj K. Agarwal, Sariel Har-peled
This paper describes a fast algorithm, based on occlusion culling, for rendering complex urban environments. Occlusion culling has been widely used to achieve interactive frame rates for rendering...
A Comment on Pseudo-Triangulation in Three (2007)
Pseudo-triangulations in two dimensions had attracted attention in computational geometry in recent years [CEG 94, PV96, Str00, ABG 01]. We present one possible extension of this concept to three...
On generalization bounds (2007)
Ashutosh Garg, Sariel Har-peled, Dan Roth
projection pro le, and margin distribution
Otfried Cheong, Sariel Har-peled, Nathan Linial
In the one-round Voronoi game, the rst player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payo for the second player is the fraction of...
Approximating extent measures of points (2007)
Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan
We present a general technique for approximating various descriptors of the extent of a set P of n points in R d. For a given extent measure and a parameter "> 0, it computes in time O(n...
On Lloyd's k-means Method (2007)
Sariel Har-peled, Bardia Sadri
We present polynomial upper and lower bounds on the number of iterations performed by Lloyd's method for k-means clustering. Our upper bounds are polynomial in the number of points, number of...
Staying in the Middle: Exact and Approximate Medians in R (2007)
And For Moving, Pankaj K. Agarwal, Mark De Berg, Jie Gao, Leonidas J. Guibas, ...
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies \in the middle" of a given point set. We study several fundamental problems of this...
Constructing Planar Cuttings in Theory and Practice (2007)
We present several variants of a new randomized incremental algorithm for computing a cutting in an arrangement of n lines in the plane. The algorithms produce cuttings whose expected size is O(r ),...
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions (2007)
Pankaj K. Agarwal, Mark De Berg, Sariel Har-peled, Mark H. Overmars, Micha Sharir, Jan Vahrenhold
d , for d = 2; 3, with a total of n vertices. We present output-sensitive algorithms for reporting all k pairs of indices (i; j) such that P i intersects P j . For the planar case we describe a...
On Finding a Guard that Sees Most and a Shop that Sells Most (2007)
Cheong, Otfried, Efrat, Alon, Har-Peled, Sariel
We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm...
Relative ε-Approximations in Geometry ∗ (2007)
Sariel Har-peled, Micha Sharir
We re-examine relative ε-approximations, previously studied in [Pol86, Hau92, LLS01, CKMS06], and their relation to certain geometric problems. We give a simple constructive proof of their existence...
Embeddings of surfaces, curves, and moving points in euclidean space (2007)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally...
Embeddings of surfaces, curves, and moving points in euclidean space (2007)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally...
The Euclidean Orienteering Problem Revisited ∗ (2007)
We consider the rooted orienteering problem: Given a set P of n points in the plane, a starting point r ∈ P, and a length constraint B, one needs to find a path starting from r that visits as many...
Embeddings of surfaces, curves, and moving points in euclidean space (2007)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
In this paper we show that dimensionality reduction (i.e., Johnson-Lindenstrauss lemma) preserves not only the distances between static points, but also between moving points, and more generally...
Covering Many or Few Points with Unit Disks (2006)
Mark Berg, Sergio Cabello, Sariel Har-peled
Let P be a set of n weighted points and let X be a constant-complexity region in the plane. We study approximation algorithms for the following two continuous facility-location problems. In the first...
Fréchet distance for curves, revisited (2006)
Boris Aronov, Sariel Har-peled, Christian Knauer, Yusu Wang, Carola Wenk
Abstract. We revisit the problem of computing the Fréchet distance between polygonal curves, focusing on the discrete Fréchet distance, where only distance between vertices is considered. We...
How to get close to the median shape (2006)
They sought it with thimbles, they sought it with care; They pursued it with forks and hope; They threatened its life with a railway-share; They charmed it with smiles and soap. – The Hunting of...
Robust shape fitting via peeling and grating coresets (2006)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
Let P be a set of n points in R d. A subset S of P is called a (k, ε)-kernel if for every direction, the direction width of S ε-approximates that of P, when k “outliers ” can be ignored in that...
How to get close to the median shape (2006)
They sought it with thimbles, they sought it with care; They pursued it with forks and hope; They threatened its life with a railway-share; They charmed it with smiles and soap. – The Hunting of...
How to get close to the median shape (2006)
They sought it with thimbles, they sought it with care; They pursued it with forks and hope; They threatened its life with a railway-share; They charmed it with smiles and soap. – The Hunting of...
Robust shape fitting via peeling and grating coresets (2006)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
Abstract Let P be a set of n points in Rd. A subset S of P is called a (k, ")-kernel if for every direction, thedirection width of S "-approximates that of P, when k...
Maximum Margin Coresets for Active and Noise Tolerant Learning (2006)
Sariel Har-peled, Dan Roth, Dav Zimak
We study the problem of learning large margin halfspaces in various settings using coresets to show that coresets are a widely applicable tool for large margin learning. A large margin coreset is a...
Robust shape fitting via peeling and grating coresets (2006)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
Let P be a set of n points in R d. A subset S of P is called a (k, ε)-kernel if for every direction, the direction width of S ε-approximates that of P, when k “outliers ” can be ignored in that...
Robust shape fitting via peeling and grating coresets (2006)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
Let P be a set of n points in R d. A subset S of P is called a (k, ε)-kernel if for every direction, the direction width of S ε-approximates that of P, when k “outliers ” can be ignored in that...
Maximum Margin Coresets for Active and Noise Tolerant Learning (2006)
Sariel Har-peled, Dan Roth, Dav Zimak
We study the problem of learning large margin halfspaces in various settings using coresets and show that coresets are a widely applicable tool for large margin learning. A large margin coreset is a...
Robust shape fitting via peeling and grating coresets (2006)
Pankaj K. Agarwal, Sariel Har-peled, Hai Yu
Let T be a set of n points in R d. We show that a (k, ε)-kernel of T of size O(k/ε (d−1)/2) can be computed in time O(n + k 2 /ε d−1), where a (k, ε)-kernel is a subset of T that...
1 Minimum Average Cost Cycle 12: Network Flow V- Min-cost flow (2006)
Version: 1.0 Let G = (V, E) be a digraph (i.e., a directed graph) with n vertices and m edges, and w: E → IR be a weight function on the edges. A directed cycle is closed walk C = (v0, v1,..., vt),...
Maximum Margin Coresets for Active and Noise Tolerant Learning (2006)
Sariel Har-peled, Dan Roth, Dav Zimak
We study the problem of learning large margin halfspaces in various settings using coresets and show that coresets are a widely applicable tool for large margin learning. A large margin coreset is a...
The Orienteering Problem in the Plane Revisited (2006)
We consider the orienteering problem: Given a set P of n points in the plane, a starting point r ∈ P, and a length constraint B, one needs to find a tour starting at r that visits as many points of...
How to get close to the median shape (2006)
They sought it with thimbles, they sought it with care; They pursued it with forks and hope; They threatened its life with a railway-share; They charmed it with smiles and soap. – The Hunting of...
Guarding galleries and terrains (2006)
Let P be a polygon with n vertices. We say that two points of P see each other if the line segment connecting them lies inside (the closure of) P. In this paper we present efficient approximation...
Relative ε-Approximations in Geometry ∗ (2006)
Sariel Har-peled, Micha Sharir
We re-examine relative ε-approximations, previously studied in [Pol86, Hau92, LLS01], [CKMS06], and their relation to certain geometric problems. We give a simple constructive proof of their...
Covering Many or Few Points with Unit Disks ∗ (2006)
Mark Berg, Sergio Cabello, Sariel Har-peled
Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems. In the first problem we want to place m unit disks, for a given...
How to get close to the median shape (2006)
They sought it with thimbles, they sought it with care; They pursued it with forks and hope; They threatened its life with a railway-share; They charmed it with smiles and soap. – The Hunting of...
A Time-Optimal Delaunay Refinement Algorithm in Two Dimensions (2005)
Har-Peled, Sariel, Ungor, Alper
We propose a new refinement algorithm to generate size-optimal quality-guaranteed Delaunay triangulations in the plane. The algorithm takes $O(n \log n + m)$ time, where $n$ is the input size and $m$...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Geometric approximation via coresets (2005)
Pankaj K. Agarwal, Sariel Har-peled, R. Varadarajan
Abstract. The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small...
Smaller coresets for k-median and k-means clustering (2005)
Sariel Har-peled, Akash Kushal
In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in ℜ d, which is of size independent of n. In particular, we construct a (k, ε)-coreset...
Geometric approximation via coresets (2005)
Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan
The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small subset Q of...
Approximation k-hop minimum-spanning trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Edgar A. Ramos, Martin Skutella
Abstract Given a complete graph on n nodes with metric edge costs, the minimum-cost k- hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest...
A uniform convergence bound for the area under the ROC curve (2005)
Shivani Agarwal, Sariel Har-peled, Dan Roth
The area under the ROC curve (AUC) has been advocated as an evaluation criterion for the bipartite ranking problem. We study uniform convergence properties of the AUC; in particular, we derive a...
Conflict-free coloring of points and simple regions in the plane (2005)
Sariel Har-peled, Shakhar Smorodinsky
We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A...
Approximating k-Hop Minimum-Spanning Trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Geographic Quorum Systems Approximations (2005)
Paz Carmi Shlomi, Shlomi Dolev, Sariel Har-peled, Matthew J. Katz, Michael Segal
Quorum systems are a mechanism for obtaining fault-tolerance and ecient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partitioning of a set X of points...
Approximating k-Hop Minimum-Spanning Trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Geographic quorum system approximations (2005)
Paz Carmi, Shlomi Dolev, Sariel Har-peled, Matthew J. Katz, Michael Segal
Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in...
On the FermatWeber center of a convex object (2005)
Paz Carmi, Sariel Har-peled, Matthew J. Katz
We show that for any convex object Q in the plane, the average distance from the Fermat-Weber center of Q to the points in Q is at least ∆(P)/7, where ∆(P) is the diameter of P, and that there...
How fast is the k-means method (2005)
Sariel Har-peled, Bardia Sadri
We present polynomial upper and lower bounds on the number of iterations performed by the k-means method (a.k.a. Lloyd’s method) for k-means clustering. Our upper bounds are polynomial in the...
Approximation algorithms for two optimal location problems in sensor networks (2005)
This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of...
On the FermatWeber center of a convex object (2005)
Paz Carmi, Sariel Har-peled, Matthew J. Katz
Abstract We show that for any convex object Q in the plane, the average distance from the Fermat-Webercenter of Q to the points in Q is at least \Delta (Q)/7, where \Delta (Q) is the diameter of Q,...
Approximation algorithms for two optimal location problems in sensor networks (2005)
Abstract — This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network...
Conflict-free coloring of points and simple regions in the plane (2005)
Sariel Har-peled, Shakhar Smorodinsky
We study conflict-free colorings, where the underlying set systems arise in geometry. Our main result is a general framework for conflict-free coloring of regions with low union complexity. A...
Approximation k-hop minimum-spanning trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost khop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Geographic quorum system approximations (2005)
Paz Carmi, Shlomi Dolev, Sariel Har-peled, Matthew J. Katz, Michael Segal
Quorum systems are a mechanism for obtaining fault-tolerance and efficient distributed systems. We consider geographic quorum systems; a geographic quorum system is a partition of a set X of sites in...
On approximating the depth and related problems (2005)
Boris Aronov, Sariel Har-peled
We study the question of finding a deepest point in an arrangement of regions, and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when...
Separability with outliers (2005)
Sariel Har-peled, Vladlen Koltun
We develop exact and approximate algorithms for computing optimal separators and measuring the extent to which two point sets in d-dimensional space are separated, with respect to different classes...
On approximating the depth and related problems (2005)
Boris Aronov, Sariel Har-peled
We study the question of finding a deepest point in an arrangement of regions, and provide a fast algorithm for this problem using random sampling, showing it sufficient to solve this problem when...
Generalization bounds for the area under the ROC curve (2005)
Shivani Agarwal, Thore Graepel, Sariel Har-peled, Ralf Herbrich, Dan Roth
We study generalization properties of the area under the ROC curve (AUC), a quantity that has been advocated as an evaluation criterion for the bipartite ranking problem. The AUC is a different term...
Smaller coresets for k-median and k-means clustering (2005)
Sariel Har-peled, Akash Kushal
In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in IR d, which is of size independent of n. In particular, we construct a (k, ε)-coreset of...
Smaller coresets for k-median and k-means clustering (2005)
Sariel Har-peled, Akash Kushal
In this paper, we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in IR d, which is of size independent of n. In particular, we construct a (k, ε)-coreset of...
Geometric approximation via coresets (2005)
Pankaj K. Agarwal, Sariel Har-peled, Kasturi R. Varadarajan
The paradigm of coresets has recently emerged as a powerful tool for efficiently approximating various extent measures of a point set P. Using this paradigm, one quickly computes a small subset Q of...
Approximation algorithms for two optimal location problems in sensor networks (2005)
This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of...
Definition 1.1 Random variable. (2005)
x given that Y = y. For example, Let role a dice. Y would be true if the number we get is even, and X would be the number we get. Then
Fast construction of nets in low dimensional metrics, and their applications (2005)
Sariel Har-peled, Manor Mendel
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms...
598shp- Randomized Algorithms (2005)
Sariel Har-peled, Las Vegas, Monte Carlo Algorithms
Definition 1.1 A Las Vegas algorithm!Las Vegas algorithm is a randomized algorithms that always return the correct result. The only variant is that it’s running time might change between...
598shp- Randomized Algorithms 1.1 About Modulo Rings and Pairwise Independence (2005)
Let p be a prime number, and let Zp = {0, 1,..., p − 1} denote the ring of integers modules p. Two integers a, b are equivalent modulo p, if a ≡ p mod p; namely, the reminder of dividing a and b...
598shp- Randomized Algorithms 1 The Johnson-Lindenstrauss lemma 1.1 Some Probability (2005)
Definition 1.1 Let N(0, 1) denote the one dimensional normal distribution. This distribution has density n(x) = e −x2 /2 / √ 2π. Let N d (0, 1) denote the d-dimensional Gaussian distribution,...
“ Do not imagine, comrades, that leadership is a pleasure! On the contrary, it is a deep and heavy responsibility. No one believes more firmly than Comrade Napoleon that all animals are equal. He...
Given an undirected graph G = (V, E) and nonnegative weights wij on the edge ij ∈ E, the maximum cut problem (MAX CUT) is that of finding the set of vertices S that maximizes the weight of the...
of the great Rastelli and juggle with thirteen balls, instead of my usual twelve, I would feel that I had truly accomplished something for my country. But I am not getting any younger, and although I...
Definition 1.1 (Variance and Standard Deviation) For a random variable X, let V[X] = E � (X − µX) 2 � = E � X 2 � − µ 2 X denote the variance of X, where µX = E[X]. Intuitively, this...
The Probabilistic Method II (2005)
“Today I know that everything watches, that nothing goes unseen, and that even wallpaper has a better memory than ours. It isn’t God in His heaven that sees all. A kitchen chair, a coat-hanger a...
Funk, Earle, A Hog on Ice and Other Curious Expressions. 1 Min Cut 1.1 Problem Definition (2005)
To acknowledge the corn- This purely American expression means to admit the losing of an argument, especially in regard to a detail; to retract; to admit defeat. It is over a hundred years old....
Sariel Har-peled, A∩b C, Pr B C, Pr N, Pr B C
At other times you seemed to me either pitiable or contemptible, eunuchs, artificially confined to an eternal childhood, childlike and childish in your cool, tightly fenced, neatly tidied playground...
‘After that he always chose out a “dog command ” and sent them ahead. It had the task of informing the inhabitants in the village where we were going to stay overnight that no dog must be...
“A drunk man will find his way home; a drunk bird may wander forever.” 1 Definitions Let G = G(V, E) be a undirected connected graph. For v ∈ V, let Γ(v) denote the neighbors of v in G. A...
“Mr. Matzerath has just seen fit to inform me that this partisan, unlike so many of them, was an authentic partisan. For- to quote the rest of my patient’s lecture- there is no such thing as a...
Approximating k-Hop Minimum-Spanning Trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, Ramos, Edgar A., Skutella, Martin
In this paper we consider the problem of computing minimum-cost spanning trees with depth restrictions. Specifically, we are given an $n$-node complete graph $G$, a metric cost-function $c$ on its...
Fast Construction of Nets in Low Dimensional Metrics, and Their Applications (2004)
Har-Peled, Sariel, Mendel, Manor
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain improved algorithms...
The One-Round Voronoi Game (2004)
Cheong, Otfried, Har-Peled, Sariel, Linial, Nathan, Matousek, Jirí
In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and near-linear time algorithm for nding the...
1.0.1 Newton’s binomial theorem (1676) We first need to extend the definition of the binomial coefficient. Definition 1.1 (Extended Binomial Coefficient) For any α ∈ IR, not necessarily integer...
VC Dimension, ε-nets and ε-approximation (2004)
“I’ve never touched the hard stuff, only smoked grass a few times with the boys to be polite, and that’s all, though ten is the age when the big guys come around teaching you all sorts to...
Coresets for k-means and k-median clustering and their applications (2004)
Sariel Har-peled, Soham Mazumdar
In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that given a point set P in...
On the Fermat-Weber Center of a Convex Object (2004)
Paz Carmi, Sariel Har-peled, Matthew J. Katz
We show that for any convex object Q in the plane, the average distance from the Fermat-Weber center of Q to the points in Q is at least #(P )/7, where #(P ) is the diameter of P , and that there...
Approximation Algorithms for Two Optimal Location Problems in Sensor Networks (2004)
This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P in the plane having approximately the largest visibility polygon inside P, and a near-linear time algorithm...
On the least median square problem (2004)
Jeff Erickson, Sariel Har-peled, David M. Mount
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
We show that coresets do not exist for the problem of 2-slabs in IR 3, thus demonstrating that the natural approach for solving approximately this problem efficiently is infeasible. On the positive...
On the least median square problem (2004)
Jeff Erickson, Sariel Har-peled, David M. Mount
We consider the exact and approximate computational complexity of the multivariate LMS linear regression estimator. The LMS estimator is among the most widely used robust linear statistical...
Coresets for k-means and k-median clustering and their applications (2004)
Sariel Har-peled, Soham Mazumdar
In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that given a point set P in...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and a nearlinear time algorithm for finding...
On finding a guard that sees most and a shop that sells most (2004)
Otfried Cheong, Alon Efrat, Sariel Har-peled
We present a near-quadratic time algorithm that computes a point inside a simple polygon P having approximately the largest visibility polygon inside P, and a nearlinear time algorithm for finding...
When Crossings Count - Approximating the Minimum Spanning Tree (2003)
Har-Peled, Sariel, Indyk, Piotr
In the first part of the paper, we present an (1+\mu)-approximation algorithm to the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of crossings...
We show that core-sets do not exist for the problem of 2-slabs in IR
Efficient algorithms for shared camera control (2003)
Sariel Har-peled, Vladlen Koltun, Dezhen Song, Ken Goldberg
We consider a system that allows n networked users to share control over a robotic webcamera. Each user guides the camera pan, tilt, and zoom, by drawing a rectangle in the user interface. The server...
Hausdorff distance under translation for points, disks, and balls (2003)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the paper, we consider two sets A, B of balls in R d, d = 2, 3, and wish to find a translation...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...
1 Previous Lecture Linear Programming II (2003)
In the previous lecture, we introduced linear programming using slack form, and we showed how to solve an LP assuming that we have a black box for solving an LP starting from a feasible solution...
High-dimensional shape fitting in linear time (2003)
Sariel Har-peled, Kasturi R. Varadarajan
Let P be a set of n points in R d. The radius of a k-dimensional at F with respect to P, denoted by RD(F; P), is dened to be max p2P dist(F; p), where dist(F; p) denotes the Euclidean distance...
Fast Algorithms for Computing the Smallest k-Enclosing Disc (2003)
Sariel Har-peled, Soham Mazumdar
We consider the problem of nding, for a given n point set P in the plane and an integer k n, the smallest circle enclosing at least k points of P . We present a randomized algorithm that computes in...
Given a set of moving points in IR , we show how to cluster them in advance, using a small number of clusters, so that at any time this static clustering is competitive with the optimal k-center...
Shape Fitting with Outliers (2003)
we present an algorithm that "-approximates the extent between the top and bottom k levels of the arrangement of H in time O(n+(k=") ), where c is a constant depending on d. The algorithm...
Fast algorithms for computing the smallest k-enclosing disc (2003)
Sariel Har-peled, Soham Mazumdar
For a set P of n points in the plane and an integer k ≤ n, consider the problem of finding the smallest circle enclosing at least k points of P. We present a randomized algorithm that computes in...
Efficient algorithms for shared camera control (2003)
Sariel Har-peled, Vladlen Koltun, Dezhen Song, Ken Goldberg
We consider a system that allows n networked users to share control over a robotic webcamera. Each user guides the camera pan, tilt, and zoom, by drawing a rectangle in the user interface. The server...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
Many divide-and-conquer based geometric algorithms and order-statistics problems ask for a point that lies “in the middle ” of a given point set. We study several fundamental problems of this...
Constraint classification for multiclass classification and ranking (2003)
Sariel Har-peled, Dan Roth, Dav Zimak
The constraint classification framework captures many flavors of multiclass classification including winner-take-all multiclass classification, multilabel classification and ranking. We present a...
Constraint classification for multiclass classification and ranking (2003)
Sariel Har-peled, Dan Roth, Dav Zimak
The constraint classification framework captures many flavors of multiclass classification including winner-take-all multiclass classification, multilabel classification and ranking. We present a...
High-dimensional shape fitting in linear time (2003)
Sariel Har-peled, Kasturi R. Varadarajan
Let P be a set of n points in Rd. The radius of a k-dimensional flat F with respect to P, denoted by RD(F, P), is defined to be maxp∈P dist(F, p), where dist(F, p) denotes the Euclidean distance...
Hausdorff distance under translation for points, disks, and balls (2003)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
We study the shape matching problem under the Hausdorff distance and its variants. In the first part of the paper, we consider two sets A, B of balls in R d, d = 2, 3, and wish to find a translation...
Constraint classification for multiclass classification and ranking (2003)
Sariel Har-peled, Dan Roth, Dav Zimak
The constraint classification framework captures many flavors of multiclass classification including winner-take-all multiclass classification, multilabel classification and ranking. We present a...
Pankaj K. Agarwal, Mark Berg, Jie Gao, Leonidas J. Guibas, Sariel Har-peled
We study the problem of “staying in the middle”: we have a set of points moving in a geometric space and wish to maintain another point (possibly one of the given points, but not necessarily)...
Projective Clustering in High Dimensions Using Core-Sets (2003)
Sariel Har-peled, Kasturi R. Varadarajan
In this paper, we show that there exists a small core-set for the problem of computing the \smallest" radius k-at for a given point-set in IR . The size of the core-set is dimension independent....
Optimally cutting a surface into a disk (2002)
Erickson, Jeff, Har-Peled, Sariel
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
Definition 1.1 A range space S is a pair (X,R), where X is a (finite or infinite) set and R is a (finite or infinite) family of�subsets � of X. �The elements of X are points and the elements of...
1.1 Some Definitions Definition 1.1 The conditional probability of X given Y is (2002)
Sariel Har-peled, An Equivalent
Paul Erdős (1913-1996)- a famous mathematician, believed that God has a book, called “The Book ” in which god maintains the perfect and most elegant mathematical proofs. Every once in a while,...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Optimally cutting a surface into a disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
Approximate Clustering via Core-Sets (2002)
Mihai Badoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently.
Near-Linear Time Approximation Algorithms for Curve Simplification (2002)
Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, Yusu Wang
We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P whose vertices are a subset of the vertices of P . The goal is to minimize the...
Computing Approximate Shortest Paths on Convex Polytopes (2002)
Pankaj K. Agarwal, Sariel Har-peled, Meetesh Karia
The algorithms for computing a shortest path on a polyhedral surface are slow, complicated, and numerically unstable. We have developed and implemented a robust and efficient algorithm for computing...
Optimally Cutting a Surface into a Disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
On Generalization Bounds, Projection Profile, and Margin Distribution (2002)
Ashutosh Garg, Sariel Har-Peled, Dan Roth
We study generalization properties of linear learning algorithms and develop a data dependent approach that is used to derive generalization bounds that depend on the margin distribution. Our method...
Optimally cutting a surface into a disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges...
A Comment on Pseudo-Triangulation in Three Dimensions (2002)
Pseudo-triangulations in two dimensions had attracted attention in computational geometry in recent years [CEG + 94, PV96, Str00, ABG + 01]. We present one possible extension of this concept to three...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Optimally cutting a surface into a disk (2002)
Jeff Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
The one-round Voronoi game (2002)
Otfried Cheong, Nathan Linial, Sariel Har-peled
In the one-round Voronoi game, the first player chooses an n-point set W in a square Q, and then the second player places another n-point set B into Q. The payoff for the second player is the...
The one-round Voronoi game (2002)
Otfried Cheong, Nathan Linial, Sariel Har-peled
In the one-round Voronoi game, the F R ST player places n sites inside a unit-square Q. Next, the SCN D player places n points inside Q. The payoff for a player is the total area of the Voronoi...
Near-linear time approximation algorithms for curve simplification (2002)
Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, Yusu Wang
We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P ′ whose vertices are a subset of the vertices of P. The goal is to minimize...
Optimally Cutting a Surface into a Disk (2002)
Je Erickson Sariel, Je Erickson, Sariel Har-peled
We consider the problem of cutting a set of edges on a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or...
On generalization bounds, projection profile, and margin distribution (2002)
Ashutosh Garg, Sariel Har-peled, Dan Roth
We study generalization properties of linear learning algorithms and develop a data dependent approach that is used to derive generalization bounds that depend on the margin distribution. Our method...
Hausdorff Distance under Translation for Points, Disks, (2002)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
Let A and B be two sets of balls in R d, d = 2, 3. We measure similarity between A and B by computing the minimum Hausdorff distance between A + t and B, where the minimum is taken either over all...
The Probabilistic Method 497- Randomized Algorithms (2002)
“Shortly after the celebration of the four thousandth anniversary of the opening of space, Angary J. Gustible discovered Gustible’s planet. The discovery turned out to be a tragic mistake....
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, T. M. Murali
We introduce two new related metrics, the geodesic width and the link width, for measuring the “distance ” between two non-intersecting polylines in the plane. If the two polylines have n...
Projective clustering in high dimensions using core-sets (2002)
Sariel Har-peled, Kasturi R. Varadarajan
In this paper, we show that there exists a small core-set for the problem of computing the “smallest ” radius k-flat for a given point-set in IR d. The size of the core-set is dimension...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Approximate clustering via core-sets (2002)
Mihai Bădoiu, Sariel Har-peled, Piotr Indyk
In this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. The...
Hausdorff Distance under Translation for Points, Disks, and Balls (2002)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Yusu Wang
Let A and B be two sets of balls in R^d, d = 2, 3. We measure similarity between A and B by computing the minimum Hausdorff distance between A+t and B, where the minimum is taken either over all...
Constraint classification: A new approach to multiclass classification and ranking (2002)
Sariel Har-peled, Dan Roth, Dav Zimak
We introduce constraint classification, a framework capturing many flavors of multiclass classification including multilabel classification and ranking, and present a meta-algorithm for learning in...
Generalization bounds for linear learning algorithms (2001)
Ashutosh Garg, Sariel Har-peled, Dan Roth
We study generalization properties of linear learning algorithms and develop a data dependent approach that is used to derive generalization bounds that depend on the margin distribution. Our method...
A practical approach for computing the diameter of a point-set (2001)
We present an approximation algorithm for computing the diameter of a point-set in d-dimensions. The new algorithm is sensitive to the \hardness " of computing the diameter of the given...
Eciently approximating the minimum-volume bounding box of a point set in three dimensions (2001)
Gill Barequet, Sariel Har-peled
We present an ecient O(n + 1="
Generalization bounds for linear learning algorithms (2001)
Ashutosh Garg, Sariel Har-peled, Dan Roth
We study generalization properties of linear learning algorithms and develop a data dependent approach that is used to derive generalization bounds that depend on the margin distribution. Our method...
Maintaining the approximate extent measures of moving points (2001)
Pankaj K. Agarwal, Sariel Har-peled
We present approximation algorithms for maintaining various descriptors of the extent of moving points in R
On-line point location in planar arrangements and its applications (2001)
Sariel Har-peled, Micha Sharir
Recently, Har-Peled [HP99b] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper, we present several applications of this...
Maintaining Approximate Extent Measures of Moving Points (2001)
Pankaj K. Agarwal, Sariel Har-peled
We present approximation algorithms for maintaining various descriptors of the extent of moving points in R . We rst describe a data structure for maintaining the smallest orthogonal rectangle...
Yehuda Afek, Anat Bremler-barr, Sariel Har-peled
We suggest a new simple forwarding technique to speed-up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6) and performs IP...
A Replacement for Voronoi Diagrams of Near Linear Size (2001)
For a set P of n points in R^d, we define a new type of space decomposition. The new diagram provides an ε-approximation to the distance function associated with the Voronoi diagram of P,...
Approximate Shape Fitting via Linearization (2001)
Sariel Har-peled, Kasturi R. Varadarajan
Shape fitting is a fundamental optimization problem in computer science. In this paper, we present a general and unified technique for solving a certain family of such problems. Given a point set P...
A replacement for Voronoi diagrams of near linear size (2001)
For a set P of n points in R d, we define a new type of space decomposition. The new diagram provides an ε-approximation to the distance function associated with the Voronoi diagram of P, while...
On-line point location in planar arrangements and its applications (2001)
Sariel Har-peled, Micha Sharir
Recently, Har-Peled [HP99b] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper, we present several applications of this...
A practical approach for computing the diameter of a point-set (2001)
We present an approximation algorithm for computing the diameter of a point-set in d-dimensions. The new algorithm is sensitive to the “hardness ” of computing the diameter of the given input,...
‘A slow sort of country! ’ said the Queen. ‘Now, HERE, you see, it takes all the running YOU can do, to keep in the same place. If you want to get somewhere else, you must run at least twice as...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
Abstract We consider the problem of locating a continuously-moving target using a group of guardsmoving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
Abstract We consider the problem of locating a moving target using a group of guards cooperatively moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon...
When crossings count - approximating the minimum spanning tree (2000)
We present an (1+")-approximation algorithm for computing the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of crossings between the...
Penetration depth of two convex polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Sweeping Simple Polygons with a Chain of Guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin, T. M. Murali
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Penetration depth of two convex polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Sweeping Simple Polygons with a Chain of Guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin, T. M. Murali
We consider the problem of locating a moving target using a group of guards cooperatively moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Morphing between Polylines (2000)
Alon Efrat, Sariel Har-peled, Leonidas J. Guibas, T. M. Murali
We study the problem of continuously transforming or morphing two non-intersecting simple (not self-intersecting) polylines in the plane. Our morphing strategies have the property that every...
Computing the Penetration Depth of Two Convex Polytopes in 3D (2000)
Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-peled, Alexander Rabinovitch, Micha Sharir
Let A and B be two convex polytopes in R 3 with m and n facets, respectively. The penetration depth of A and B, denoted as (A; B), is the minimum distance by which A has to be translated so that A...
Constructing Planar Cuttings in Theory and Practice (2000)
We present a new randomized incremental algorithm for computing a cutting in an arrangement of lines in the plane. The algorithm produce cuttings whose expected size is O(r 2 ), and the expected...
Maintaining the Approximate Extent Measures of Moving Points (2000)
Pankaj K. Agarwal, Sariel Har-peled
We present approximation algorithms for maintaining various descriptors of the extent of moving points in R d . We first describe a data structure for maintaining the smallest orthogonal rectangle...
When crossings count - approximating the minimum spanning tree (2000)
We present an (1+ε)-approximation algorithm for computing the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of crossings between the spanning tree...
Sweeping simple polygons with a chain of guards (2000)
Alon Efrat, Leonidas J. Guibas, Sariel Har-peled, David C. Lin
We consider the problem of locating a continuously-moving target using a group of guards moving inside a simple polygon. Our guards always form a simple polygonal chain within the polygon such that...
Y.: Near-linear time approximation algorithms for path simplification (2000)
Pankaj K. Agarwal, Sariel Har-peled, Nabil H. Mustafa, Yusu Wang
Abstract. We consider the problem of approximating a polygonal curve under a given error criterion by another polygonal curve whose vertices are a subset of the vertices of. The goal is to minimize...
Yehuda Afek, Anat Bremler-barr, Sariel Har-peled
We suggest a new simple forwarding technique to speed-up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6) and performs IP...
Taking a Walk in a Planar Arrangement (1999)
We present a new randomized algorithm for computing portions of an arrangement of n arcs in the plane, each pair of which intersect in at most t points. We use this algorithm to perform online walks...
On-line Point Location in Planar Arrangements and Its Applications (1999)
Sariel Har-peled, Micha Sharir
Recently, Har-Peled [HP99b] presented a new randomized technique for online construction of the zone of a curve in a planar arrangement of arcs. In this paper, we present several applications of this...
Computing Approximate Shortest Paths on Convex Polytopes (1999)
Pankaj K. Agarwal, Sariel Har-peled, Meetesh Karia
polyhedral Ç¥¸é¿¡ °¡Àå ªÀº °æ·Î¸¦ °è»êÇϱ⸦ À§ÇØ »ê¹ýÀº ´À¸®°í, º¹ÀâÇÏ´Ù,±×¸®°í ¼öÀûÀ¸·Î ºÒ¾ÈÁ¤ÇÑ. ¿ì¸®´Â convex...
Approximation and Exact Algorithms for Minimum-Width Annuli and Shells (1999)
Pankaj K. Agarwal, Boris Aronov, Sariel Har-peled, Micha Sharir
Let S be a set of n points in R d . The "roundness" of S can be measured by computing the width ! = ! (S) of the thinnest spherical shell (or annulus in R 2 ) that contains S. This paper...
On-line Zone Construction in Arrangements of Lines in the Plane (1999)
Yuval Aharoni Dan, Dan Halperin, Iddo Hanniel, Sariel Har-peled, Chaim Linhart
. Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that...
When Crossings Count - Approximating the Minimum Spanning Tree (1999)
In the first part of the paper, we present an (1 + ε)-approximation algorithm to the minimum-spanning tree of points in a planar arrangement of lines, where the metric is the number of...
Anat Bremler-barr, Yehuda Afek, Sariel Har-peled
We suggest a new simple forwarding technique to speed-up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6) and performs IP...
On-line zone construction in arrangements of lines in the plane (1999)
Chaim Linhart, Dan Halperin, Sariel Har-Peled, Iddo Hanniel
Given a finite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that...
On-line Zone Construction in Arrangements of Lines in the Plane (1999)
Yuval Aharoni, Dan Halperin, Iddo Hanniel, Sariel Har-peled, Chaim Linhart
. Given a nite set L of lines in the plane we wish to compute the zone of an additional curve in the arrangement A(L), namely the set of faces of the planar subdivision induced by the lines in L that...
Yehuda Afek, Anat Bremler-barr, Sariel Har-peled
We suggest a new simple forwarding technique to speed-up IP destination address lookup. The technique is a natural extension of IP, requires 5 bits in the IP header (IPv4, 7 in IPv6) and performs IP...
Efficiently approximating the minimum-volume bounding box of a point set in three dimensions (1999)
Gill Barequet, Sariel Har-peled
We present an efficient O(n + 1/ε 4.5)-time algorithm for computing a (1 + ε)approximation of the minimum-volume bounding box of n points in R 3. We also present a simpler algorithm (for the same...
Taking a walk in a planar arrangement (1999)
We present a randomized algorithm for computing portions of an arrangement of n arcs in the plane, each pair of which intersect in at most t points. We use this algorithm to perform online walks...
Constructing approximate shortest path maps in three dimensions (1999)
We present a new technique for constructing a data-structure that approximates shortest path maps in IR d. By applying this technique, we get the following two results on approximate shortest path...
An On-Line Occlusio-Culling Algorithm for Fast Walkthrough in Urban Areas (1998)
Wang, Yusu, Agarwal, Pankaj K., Har-Peled, Sariel
We describe a fast algorithm to speed up rendering of scenes for walkthroughs in urban environments. Our occlusion culling algorithm takes advantage of temporal coherence in image space. As such,...
Results on k-sets and j-facets via continuous motion (1998)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR
Gill Barequet, Sariel Har-peled
The 3sum problem represents a class of problems conjectured to require \Omega\Gamma n 2 ) time to solve, where n is the size of the input. Given two simple polygons P and Q in the plane, we show that...
Fly Cheaply: On the Minimum Fuel-Consumption Problem (1998)
Introduction Assume we wish to plan a path of a flight, starting at an airport s (i.e. Tel-Aviv), and our destination is the airport t (i.e. Minneapolis). Our plane is able to carry enough fuel, so a...
Approximating Shortest Paths on a Convex Polytope in Three Dimensions (1997)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Kasturi R. Varadarajan
Given a convex polytope P with n faces in IR 3 , points s; t 2 @P , and a parameter 0 ! " 1, we present an algorithm that constructs a path on @P from s to t whose length is at most (1+ ")d...
An Output Sensitive Algorithm for Discrete Convex Hulls (1997)
Given a convex body C in the plane, its discrete hull is C 0 = ConvexHull(C " L), where L = ZZ \Theta ZZ is the integer lattice. We present an O(jC 0 j log ffi(C))-time algorithm for calculating...
On the Expected Complexity of Random Convex Hulls (1997)
In this paper we present several results on the expected complexity of a convex hull of n points chosen uniformly and independently from a convex shape. (i) We show that the expected number of...
Results on k-Sets and j-Facets via Continuous Motion (1997)
Artur Andrzejak, Boris Aronov, Sariel Har-peled, Raimund Seidel, Emo Welzl
Let P be a set of n points in IR d in general position, i.e., no i + 1 points on a common (i \Gamma 1)-flat, 1 i d. A k-set of P is a set S of k points in P that can be separated from P nS by a...
Approximate Shortest-Path and Geodesic Diameter on Convex Polytopes in Three Dimensions (1996)
Given a convex polytope P with n edges in IR 3 , we present a relatively simple algorithm that preprocesses P in O(n) time, such that, given any two points s; t 2 @P , and a parameter 0 ! " 1,...
Approximating Shortest Paths on a Convex Polytope in Three Dimensions (1996)
Pankaj K. Agarwal, Sariel Har-peled, Micha Sharir, Kasturi R. Varadarajan
Given a convex polytope P with n faces in IR 3 , points s; t 2 @P , and a parameter 0 ! " 1, we present an algorithm that constructs a path on @P from s to t whose length is at most (1+")d...
The Complexity of One or Many Faces in the Overlay of Many Arrangements (1995)
We present an extension of the Combination Lemma of [GSS89] that expresses the complexity of one or several faces in the overlay of many arrangements, as a function of the number of arrangements, the...
The Complexity of a Single Face of a Minkowski Sum (1995)
Sariel Har-peled, Timothy M. Chan, Boris Aronov, Dan Halperin, Jack Snoeyink
This note considers the complexity of a free region in the configuration space of a polygonal robot translating amidst polygonal obstacles in the plane. Specifically, given polygonal sets P and Q...
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
Gill Barequet, Sariel Har-peled
We present an efficient randomized O(n log n+1=" 4:5 ) expected-time algorithm for computing an "-approximation of the minimum-volume bounding box of n points in IR 3 . We also present a...
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
Gill Barequet, Sariel Har-peled
We present an efficient O(n + 1=" 4:5 ) time algorithm for computing an (1+")-approximation of the minimum-volume bounding box of n points in IR 3 . We also present a simpler algorithm (for...