DOC PREVIEW
Duke CPS 296.2 - Geometric Approximation via Coresets

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Geometric Approximation via Coresets∗Pankaj K. Agarwal†Sariel Har-Peled‡Kasturi R. Varadarajan§October 22, 20 0 4AbstractThe paradigm of coresets has recently emerged as a powerful tool for efficiently approximatingvarious extent measures of a point set P . Using this paradigm, one quickly computes a small subset Qof P , called a coreset, that approximates the original set P and and then solves the problem on Q usinga relatively inefficient algorithm. The solution for Q is then translated to an approx imate solution to theoriginal point set P . This paper describes the ways in which this paradigm has been successfully appliedto various optimization and extent measure problems.1 IntroductionOne of the classical techniques in developing approximation algorithms is the extraction of “small” amountof “most relevant” information from the given data, and performing the computation on this extracted data.Examples of the use of this technique in a geometric context include random sampling [18, 49], convexapproximation [27, 14], surface simplification [43], feature extraction and shape descriptors [26, 24]. Forgeometric problems where the input is a set of points, the question reduces to finding a small subset (i.e.,coreset) of the points, such that one can perform the desired computation on the coreset.As a concrete example, consider the problem of computing the diameter of a point set. Here it is clearthat, in the worst case, classical sampling techniques like ε-approximation and ε-net would fail to computea subset of points that contain a good approximation to the diameter [52, 42]. While in this problem it isclear that convex approximation (i.e., an approximation of the convex hull of the point set) is helpful andprovides us w ith the desired coreset, convex approximation of the point set is not useful for computing thenarrowest annulus containing a point set in the plane.In this paper, we describe several recent results which employ the idea of coresets to develop efficientapproximation algorithms for various geometric problems. In particular, motivated by a variety applications,considerable work has been done on measuring various descriptors of the extent of a set P of n pointsin Rd. We refer to such measures as extent measures of P . Roughly speaking, an extent measure of Peither computes certain statistics of P itself or of a (possibly nonconvex) geometric shape (e.g. sphere, box,cylinder, etc.) enclosing P . Examples of the former include computing the kth largest distance between∗Research by the first author is supported by NSF under grants CCR-00-86013, EIA-98-70724, EIA-01-31905, and CCR-02-04118, and by a grant from the U.S.–Israel Binational Science Foundation. R esearch by the second author is supported by NSFCAREER award CCR-0132901. Research by the third author is supported by NSF CAREER award CCR-0237431†Department of Computer Science, Box 90129, Duke University, Durham NC 27708-0129; [email protected] du;http://www.cs. duke.edu/˜pankaj/‡Department of Computer Science, DCL 2111; University of Illinois; 1304 West Springfield Ave., Urbana, IL 61801;[email protected] u; http://www.uiuc.edu/˜sariel/§Department of Computer Science, T he University of Iowa, Iowa City, IA 52242-1419; [email protected];http://www.cs. uiowa.edu/˜kvaradar/1pairs of points in P, and the examples of the latter include computing the smallest radius of a sphere (orcylinder), the minimum volume (or surface area) of a box, and the smallest width of a slab (or a spherical orcylindrical shell) that contain P . There has also been some recent work on maintaining extent measures ofa set of moving points [2].Shape fitting, a fundamental problem in computational geometry, computer vision, machine learning,data mining, and many other areas, is closely related to computing extent measures. A widely used shape-fitting problem asks for finding a shape that best fits P under some “fitting” criterion. A typical criterion formeasuring how well a shape γ fits P, denoted as µ(P , γ), is the maximum distance between a point of Pand its nearest point on γ, i.e., µ(P, γ) = maxp∈Pminq∈γ!p − q!. Then one can define the extent measureof P to be µ(P ) = minγµ(P, γ), where the minimum is taken over a family of shapes (such as points,lines, hyperplanes, spheres, etc.). For example, the problem of finding the minimum radius sphere (resp.cylinder) enclosing P is the same as finding the point (resp. line) that fits P best, and the problem of findingthe smallest width slab (resp. spherical shell, cylindrical shell)1is the same as finding the hyperplane (resp.sphere, cylinder) that fits P best.The exact algorithms for computing extent measures are generally expensive, e.g., the best known al-gorithms for computing the smallest volume bounding box containing P in R3run in O(n3) time. Con-sequently, attention has shifted to developing approximation algorithms [11]. The goal is to compute anε-approximation, for some 0 < ε < 1, of the extent measure in roughly O(nf(ε)) or even O(n + f(ε))time, that is, in time near-linear or linear in n. The framework of coresets has recently emerged as a generalapproach to achieve this goal. For any extent measure µ and an input point set P for which we wish to com-pute the extent measure, the general idea is to argue that there exists an easily computable subset Q ⊆ P ,called a coreset, of size 1/εO(1), so that solving the underlying problem on Q gives an approximate solutionto the original problem. For example, if µ(Q) ≥ (1 −ε)µ(P), then this approach gives an approximation tothe extent measure of P . In the context of shape fitting, an appropriate property for Q is that for any shapeγ from the underlying family, µ(Q, γ) ≥ (1 − ε)µ(P, γ). With this property, the approach returns a shapeγ∗that is an approximate best fit to P .Following earlier work [11, 16, 55] that hinted at the generality of this approach, Agarwalet al.[3]provided a formal framework by introducing the notion of ε-kernel and showing that it yields a coreset formany optimization problems. They also showed that this technique yields approximation algorithms fora wide range of problems. Since the appearance of preliminary versions of their work, many subsequentpapers have used a coreset based approach for other geometric optimization problems, including clusteringand other extent-measure problems [6, 15, 10, 40, 47, 48].In this paper, we have attempted to


View Full Document

Duke CPS 296.2 - Geometric Approximation via Coresets

Download Geometric Approximation via Coresets
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Geometric Approximation via Coresets and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Geometric Approximation via Coresets 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?