Article

How to get close to the median shape

Author:

Sariel Har-PeledAuthors Info & Claims

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

Pages 402 - 410

https://doi.org/10.1145/1137856.1137915

Published: 05 June 2006 Publication History

Abstract

In this paper, we study the problem of L₁-fitting a shape to a set of n points in R^d (where d is a fixed constant), where the target is to minimize the sum of distances of the points to the shape, or alternatively the sum of squared distances. We present a general technique for computing a (1+ε)-approximation for such a problem, with running time O(n+poly(log n, 1/ε)), where poly(log n, 1/ε) is a polynomial of constant degree of log n and 1/ε (the power of the polynomial is a function of d). This is a linear time algorithm for a fixed ε>0, and is the first subquadratic algorithm for this problem.Applications of the algorithm include best fitting either a circle, a sphere or a cylinder to a set of points when minimizing the sum of distances (or squared distances) to the respective shape.

References

[1]

P. Agarwal, S. Har-Peled, and H. Yu. Robust shape fitting via peeling and grating coresets. In Proc. 17th ACM-SIAM Sympos. Discrete Algorithms, pages 182--191, 2006.

Digital Library

[2]

P. K. Agarwal, B. Aronov, S. Har-Peled, and M. Sharir. Approximation and exact algorithms for minimum-width annuli and shells. Discrete Comput. Geom., 24(4):687--705, 2000.

Digital Library

[3]

P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. J. Assoc. Comput. Mach., 51(4):606--635, 2004.

Digital Library

[4]

P. K. Agarwal and J. Matoušek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:393--418, 1994.

Digital Library

[5]

G. Barequet and S. Har-Peled. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms, 38:91--109, 2001.

Digital Library

[6]

T. M. Chan. Approximating the diameter, width, smallest enclosing cylinder and minimum-width annulus. Internat. J. Comput. Geom. Appl., 12(2):67--85, 2002.

[7]

K. L. Clarkson. Subgradient and sampling algorithms for l1 regression. In Proc. 16th ACM-SIAM Sympos. Discrete Algorithms, pages 257-266, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics.

Digital Library

[8]

A. Deshpande, L. Rademacher, S. Vempala, and G. Wang. Matrix approximation and projective clustering via volume sampling. In Proc. 17th ACM-SIAM Sympos. Discrete Algorithms, pages 1117--1126, New York, NY, USA, 2006. ACM Press.

Digital Library

[9]

A. Frieze, R. Kannan, and S. Vempala. Fast monte-carlo algorithms for finding low-rank approximations. J. Assoc. Comput. Mach., 51(6):1025--1041, 2004.

Digital Library

[10]

J. Gao, M. Langberg, and L. Schulman. Analysis of incomplete data and an intrinsic-dimension helly theorem. In Proc. 17th ACM-SIAM Sympos. Discrete Algorithms, pages 464--473, 2006.

Digital Library

[11]

S. Har-Peled. How to get close to the median shape. Available from http://www.uiuc.edu/~sariel/papers/05/l1fitting/, 2006.

[12]

S. Har-Peled and V. Koltun. Separability with outliers. In Proc. 16th Annu. Internat. Sympos. Algorithms Comput., pages 28--39, 2005.

Digital Library

[13]

S. Har-Peled and A. Kushal. Smaller coresets for k-median and k-means clustering. In Proc. 21st Annu. ACM Sympos. Comput. Geom., pages 126--134, 2005.

Digital Library

[14]

S. Har-Peled and S. Mazumdar. Coresets for k-means and k-median clustering and their applications. In Proc. 36th Annu. ACM Sympos. Theory Comput., pages 291--300, 2004.

Digital Library

[15]

S. Har-Peled and Y. Wang. Shape fitting with outliers. SIAM J. Comput., 33(2):269--285, 2004.

Digital Library

[16]

J. O'Rourke. Finding minimal enclosing boxes. Internat. J. Comput. Inform. Sci., 14:183--199, 1985.

[17]

G. Seber and C. Wild. Nonlinear Regression. John Wiley & Sons, 1989.

[18]

P. Yamamoto, K. Kato, K. Imai, and H. Imai. Algorithms for vertical and orthogonal l1 linear approximation of points. In Proc. 4th Annu. ACM Sympos. Comput. Geom., pages 352--361. ACM Press, 1988.

Digital Library

[19]

Y. Zhou and S. Suri. Algorithms for a minimum volume enclosing simplex in three dimensions. SIAM J. Comput., 31(5):1339--1357, 2002.

Digital Library

Cited By

Epstein DFeldman D(2020)Sphere Fitting with Applications to Machine TrackingAlgorithms10.3390/a1308017713:8(177)Online publication date: 22-Jul-2020
https://doi.org/10.3390/a13080177
David RGoldenberg EKrauthgamer R(2017)Local reconstruction of low-rank matrices and subspacesRandom Structures & Algorithms10.1002/rsa.2072051:4(607-630)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1002/rsa.20720
Ding HXu JCheng SDevillers O(2014)Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related ProblemsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582131(110-119)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582131
Show More Cited By

Index Terms

How to get close to the median shape
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

How to get close to the median shape
Special issue on the 21st European workshop on computational geometry (EWCG 2005)

In this paper, we study the problem of L₁-fitting a shape to a set of n points in R^d (where d is a fixed constant), where the target is to minimize the sum of distances of the points to the shape, or alternatively the sum of squared distances. We ...
A deterministic algorithm for fitting a step function to a weighted point-set

Given a set of n points in the plane, each point having a positive weight, and an integer k>0, we present an optimal O(nlogn)-time deterministic algorithm to compute a step function with k steps that minimizes the maximum weighted vertical distance to ...
Approximation Algorithms for a k-Line Center

Given a set P of n points in źd and an integer k ź 1, let w* denote the minimum value so that P can be covered by k congruent cylinders of radius w*. We describe a randomized algorithm that, given P and an ź > 0, computes k cylinders of radius (1 + ź) w*...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

June 2006

500 pages

ISBN:1595933409

DOI:10.1145/1137856

Program Chairs:
Nina Amenta
University of California at Davis
,
Otfried Cheong
Korea Advanced Institute of Science and Technology

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG06

Sponsor:

SoCG06: 22nd Annual Symposium on Computational Geometry

June 5 - 7, 2006

Arizona, Sedona, USA

Acceptance Rates

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
172
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Epstein DFeldman D(2020)Sphere Fitting with Applications to Machine TrackingAlgorithms10.3390/a1308017713:8(177)Online publication date: 22-Jul-2020
https://doi.org/10.3390/a13080177
David RGoldenberg EKrauthgamer R(2017)Local reconstruction of low-rank matrices and subspacesRandom Structures & Algorithms10.1002/rsa.2072051:4(607-630)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1002/rsa.20720
Ding HXu JCheng SDevillers O(2014)Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related ProblemsProceedings of the thirtieth annual symposium on Computational geometry10.1145/2582112.2582131(110-119)Online publication date: 8-Jun-2014
https://dl.acm.org/doi/10.1145/2582112.2582131
Shyamalkumar NVaradarajan KGabow H(2007)Efficient subspace approximation algorithmsProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283440(532-540)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283440
Deshpande AVaradarajan KJohnson DFeige U(2007)Sampling-based dimension reduction for subspace approximationProceedings of the thirty-ninth annual ACM symposium on Theory of computing10.1145/1250790.1250884(641-650)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.1145/1250790.1250884
Har-Peled S(2006)Coresets for discrete integration and clusteringProceedings of the 26th international conference on Foundations of Software Technology and Theoretical Computer Science10.1007/11944836_6(33-44)Online publication date: 13-Dec-2006
https://dl.acm.org/doi/10.1007/11944836_6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents