Pankaj K. Agarwal
Skip Abstract Section
Abstract
We present a general technique for approximating various descriptors of the extent of a set P of n points in Rd when the dimension d is an arbitrary fixed constant. For a given extent measure μ and a parameter ε > 0, it computes in time O(n + 1/εO(1)) a subset Q ⊆ P of size 1/εO(1), with the property that (1 − ε)μ(P) ≤ μ(Q) ≤ μ(P). The specific applications of our technique include ε-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P, (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P. Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.
- Agarwal, P. K., Arge, L., and Erickson, J. 2003. Indexing moving points. J. Comput. Syst. Sci. 66, 207--243. Google Scholar
- Agarwal, P. K., Aronov, B., Har-Peled, S., and Sharir, M. 2000. Approximation and exact algorithms for minimum-width annuli and shells. Disc. Comput. Geom. 24, 4, 687--705.Google Scholar
- Agarwal, P. K., Aronov, B., and Sharir, M. 2001a. Exact and approximation algorithms for minimum-width cylindrical shells. Disc. Comput. Geom. 26, 3, 307--320.Google Scholar
- Agarwal, P. K., Guibas, L. J., Hershberger, J., and Veach, E. 2001b. Maintaining the extent of a moving point set. Disc. Comput. Geom. 26, 3, 353--374.Google Scholar
- Agarwal, P. K., and Matoušek, J. 1994. On range searching with semialgebraic sets. Disc. Comput. Geom. 11, 393--418.Google Scholar
- Agarwal, P. K., and Matoušek, J. 2004. Discretizing the space of directions. in preparation.Google Scholar
- Agarwal, P. K., Procopiuc, C. M., and Varadarajan, K. 2002. Approximation algorithms for k-line center. In Proceedings of the 10th Annual Symposium on European Algorithms. 54--63. Google Scholar
- Agarwal, P. K., and Sharir, M. 1998. Efficient algorithms for geometric optimization. ACM Comput. Surv. 30, 412--458. Google Scholar
- Agarwal, P. K., and Sharir, M. 2000. Arrangements and their applications. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier Science Publishers B.V. North-Holland, Amsterdam, The Netherlands, 49--119.Google Scholar
- Barequet, G., and Har-Peled, S. 2001. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms 38, 91--109. Google Scholar
- Basch, J., Guibas, L. J., and Hershberger, J. 1999. Data structures for mobile data. J. Algorithms 31, 1, 1--28. Google Scholar
- Bentley, J. L., and Saxe, J. B. 1980. Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms 1, 301--358.Google Scholar
- Bronshteyn, E. M., and Ivanov, L. D. 1976. The approximation of convex sets by polyhedra. Siberian Math. J. 16, 852--853.Google Scholar
- Bădoiu, M., and Clarkson, K. 2003. Smaller core-sets for balls. In Proceedings of the 14th Annual ACM--SIAM Symposium on Discrete Algorithms. 801--802. Google Scholar
- Bădoiu, M., Har-Peled, S., and Indyk, P. 2002. Approximate clustering via core-sets. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing. 250--257. Google Scholar
- Chan, T. M. 2002. Approximating the diameter, width, smallest enclosing cylinder and minimum-width annulus. Int. J. Comput. Geom. Appl. 12, 2, 67--85.Google Scholar
- Chazelle, B., and Matoušek, J. 1996. On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms 21, 579--597. Google Scholar
- Chen, Y., Dong, G., Han, J., Wah, B. W., and Wang, J. 2002. Multi-dimensional regression analysis of time-series data streams. In Proceedings of the 28th International Conference on Very Large Data Bases. 323--334. Google Scholar
- Dudley, R. M. 1974. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory 10, 3, 227--236.Google Scholar
- Duncan, C. A., Goodrich, M. T., and Ramos, E. A. 1997. Efficient approximation and optimization algorithms for computational metrology. In Proceedings of the 8th ACM--SIAM Symposium on Discrete Algorithms. ACM, New York, 121--130. Google Scholar
- Gärtner, B. 1995. A subexponential algorithm for abstract optimization problems. SIAM J. Comput. 24, 1018--1035. Google Scholar
- Gritzmann, P., and Klee, V. 1992. Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Disc. Comput. Geom. 7, 255--280. Google Scholar
- Guha, S., Koudas, N., and Shim, K. 2001. Data-streams and histograms. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing. ACM, New York, 471--475. Google Scholar
- Guha, S., Mishra, N., Motwani, R., and O'Callaghan, L. 2000. Clustering data streams. In Proceedings of the 41th Annual IEEE Symposium on Foundation of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 359--366. Google Scholar
- Har-Peled, S., and Wang, Y. 2003. Shape fitting with outliers. In Proceedings of the 19th Annual ACM Symposium on Computer Geometry. ACM, New York, 29--38. Google Scholar
- Korn, F., Muthukrishnan, S., and Srivastava, D. 2002. Reverse nearest neighbour aggregates over data streams. In Proceedings of the 28th International Conference on Very Large Data Bases. 814--825. Google Scholar
- Kumar, P., Mitchell, J., and Yildirim, E. 2003. Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions. In Proc. 5th Workshop on Algorithm Engineering and Experiments 45--55.Google Scholar
- Kumar, P., and Yildirim, E. 2003. Approximating minimum volume enclosing ellipsoids using core sets. Unpublished manuscript.Google Scholar
- Munro, J. I., and Paterson, M. S. 1980. Selection and sorting with limited storage. Theoret. Comput. Sci. 12, 315--323.Google Scholar
- O'Rourke, J. 1985. Finding minimal enclosing boxes. Int. J. Comput. Inf. Sci. 14, 183--199.Google Scholar
- Procopiuc, C. M., Agarwal, P. K., and Har-Peled, S. 2002. STAR-Tree: An efficient self-adjusting index for moving objects. In Proc. 4th Workshop on Algorithm Engineering and Experiments, D. M. Mount and C. Stein, Eds. Lecture Notes in Computer Science, vol. 2409. Springer-Verlag, New York, 178--193. Google Scholar
- Saltenis, S., Jensen, C. S., Leutenegger, S., and Lopez, M. 2000. Indexing the positions of continuously moving objects. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, New York, 331--342. Google Scholar
- Yao, A. C., and Yao, F. F. 1985. A general approach to D-dimensional geometric queries. In Proceedings of the 17th Annual ACM Symposium on Theory Computing. ACM, New York, 163--168. Google Scholar
- Zhou, Y., and Suri, S. 2002. Algorithms for a minimum volume enclosing simplex in three dimensions. SIAM J. Comput. 31, 5, 1339--1357. Google Scholar
Index Terms
- Approximating extent measures of points
Recommendations
Comparison of Distance Measures for Planar Curves
The Hausdorff distance is a very natural and straightforward distance measure for comparing geometric shapes like curves or other compact sets. Unfortunately, it is not an appropriate distance measure in some cases. For this reason, the Fréchet distance ...
Approximating Tverberg Points in Linear Time for Any Fixed Dimension
Let $$P \subseteq \mathbb{R }^d$$P⊆Rd be a $$d$$d-dimensional $$n$$n-point set. A Tverberg partition is a partition of $$P$$P into $$r$$r sets $$P_1, \dots , P_r$$P1,ź,Pr such that the convex hulls $$\hbox {conv}(P_1), \dots , \hbox {conv}(P_r)$$conv(P1)...
Approximating k-node Connected Subgraphs via Critical Graphs
We present two new approximation algorithms for the problem of finding a k-node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were $O(\min \{k,\frac{n}{\sqrt{n-k}}\})$ for ...
Comments