article

Space Exploration via Proximity Search

Authors:

Sariel Har-Peled,

David M. Mount,

Benjamin RaichelAuthors Info & Claims

Discrete & Computational Geometry, Volume 56, Issue 2

Pages 357 - 376

https://doi.org/10.1007/s00454-016-9801-7

Published: 01 September 2016 Publication History

Abstract

We investigate what computational tasks can be performed on a point set in $${\mathbb {R}}^d$$Rd, if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following:(A)One can compute an approximate bi-criteria k-center clustering of the point set, and more generally compute a greedy permutation of the point set.(B)One can decide if a query point is (approximately) inside the convex-hull of the point set. We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set.

References

[1]

Andersson, L.-E., Stewart, N.F.: Introduction to the Mathematics of Subdivision Surfaces. SIAM, Philadelphia (2010)

Digital Library

[2]

Barman, S.: Approximating nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory's theorem. In: Proceedings of 47th Annual Symposium on the Theory of Computing (STOC), pp. 361---369 (2015)

Digital Library

[3]

Basu, S., Pollack, R., Roy, M.F.: Algorithms in Real Algebraic Geometry. Algorithms and Computation in Mathematics. Springer, Berlin (2006)

Digital Library

[4]

Binnig, G., Quate, C.F., Gerber, Ch.: Atomic force microscope. Phys. Rev. Lett. 56, 930---933 (1986)

[5]

Blinn, J.F.: A generalization of algebraic surface drawing. ACM Trans. Graph. 1, 235---256 (1982)

Digital Library

[6]

Boissonnat, J.-D., Guibas, L.J., Oudot, S.: Learning smooth shapes by probing. Comput. Geom. Theory Appl. 37(1), 38---58 (2007)

Digital Library

[7]

Clarkson, K.L.: Coresets, sparse greedy approximation, and the Frank---Wolfe algorithm. ACM Trans. Algorithms 6(4), 63 (2010)

Digital Library

[8]

Cole, R., Yap, C.K.: Shape from probing. J. Algorithms 8(1), 19---38 (1987)

Digital Library

[9]

Feder, T., Greene, D. H.: Optimal algorithms for approximate clustering. In: Proceedings of 20th Annual ACM Aymposium on Theory of computing (STOC), pp. 434---444 (1988)

Digital Library

[10]

Goel, A., Indyk, P., Varadarajan, K. R.: Reductions among high dimensional proximity problems. In: Proceedings of 12th ACM---SIAM Symposium on Discrete Algorithms (SODA), pp. 769---778, (2001)

Digital Library

[11]

Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293---306 (1985)

[12]

Har-Peled, S.: Geometric Approximation Algorithms. Mathematical Surveys and Monographs, vol. 173. American Mathematical Society, Providence (2011)

Digital Library

[13]

Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. Theory Comput. 8, 321---350 (2012). Special issue in honor of Rajeev Motwani

[14]

Har-Peled, S., Kumar, N., Mount, D., Raichel, B.: Space exploration via proximity search. CoRR, http://arxiv.org/abs/1412.1398 (2014)

[15]

Har-Peled, S., Mendel, M.: Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput. 35(5), 1148---1184 (2006)

Digital Library

[16]

Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 39, 2nd edn, pp. 877---892. CRC Press, Boca Raton (2004)

[17]

Kalantari, B.: A characterization theorem and an algorithm for a convex hull problem. Ann. Oper. Res. 226(1), 301---349 (2015)

[18]

Mandelbrot, B.B.: The Fractal Geometry of Nature. Macmillan, New York (1983)

[19]

Matoušek, J., Seidel, R., Welzl, E.: How to net a lot with little: small $$\varepsilon $$¿-nets for disks and halfspaces. In: Proceedings of 6th Annual ACM Symposium on Computational Geometry (SoCG), pp. 16---22 (1990)

Digital Library

[20]

Mulvey, J.M., Beck, M.P.: Solving capacitated clustering problems. Eur. J. Oper. Res. 18, 339---348 (1984)

[21]

Novikoff, A.B.J.: On convergence proofs on perceptrons. Proc. Symp. Math. Theo. Automata 12, 615---622 (1962)

[22]

Panahi, F., Adler, A., van der Stappen, A. F., Goldberg, K.: An efficient proximity probing algorithm for metrology. In: Proceedings of IEEE International Conference on Automation Science and Engineering (CASE), pp. 342---349 (2013)

[23]

Smelik, R. M., De Kraker, K. J., Groenewegen, S. A., Tutenel, T., Bidarra, R.: A survey of procedural methods for terrain modelling. In: Proceedings of the CASA. Workshop on 3D Advanced Media In Gaming and Simulation (2009)

[24]

Skiena, S.S.: Problems in geometric probing. Algorithmica 4, 599---605 (1989)

[25]

Skiena, S.S.: Geometric reconstruction problems. In: Goodman, J.E., O'Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chapter 26, pp. 481---490. CRC Press LLC, Boca Raton (1997)

Digital Library

[26]

Wikipedia. Atomic force microscopy--Wikipedia, The Free Encyclopedia (2014)

Cited By

Agarwal PEsmailpour AHu XSintos SYang J(2024)Computing A Well-Representative Summary of Conjunctive Query ResultsProceedings of the ACM on Management of Data10.1145/36958352:5(1-27)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695835
Har-Peled SJones MRahul S(2021)Active-Learning a Convex Body in Low DimensionsAlgorithmica10.1007/s00453-021-00807-w83:6(1885-1917)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00453-021-00807-w

Space Exploration via Proximity Search
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Robust Proximity Search for Balls Using Sublinear Space

Given a set of n disjoint balls $$b_1, \dots , b_n$$b1,ź,bn in $$\mathrm{I\! R}^d$$IRd, we provide a data structure of near linear size that can answer $$(1\pm {\varepsilon })$$(1 ź)-approximate kth-nearest neighbor queries on the balls in $$O(\log n + ...
On objective-based rough c-means clustering
GRC '12: Proceedings of the 2012 IEEE International Conference on Granular Computing (GrC-2012)

Conventional clustering algorithms classify a set of objects into some clusters with clear boundaries, that is, one object must belong to one cluster. However, many objects belong to more than one cluster in real world, since the boundaries of clusters ...
A simple statistics-based nearest neighbor cluster detection algorithm

We propose a new method for autonomously finding clusters in spatial data. The proposed method belongs to the so called nearest neighbor approaches for finding clusters. It is a repetitive technique which produces changing averages and deviations of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete & Computational Geometry

Discrete & Computational Geometry Volume 56, Issue 2

September 2016

253 pages

ISSN:0179-5376

Issue’s Table of Contents

Copyright © Copyright © 2016 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 September 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 29 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal PEsmailpour AHu XSintos SYang J(2024)Computing A Well-Representative Summary of Conjunctive Query ResultsProceedings of the ACM on Management of Data10.1145/36958352:5(1-27)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695835
Har-Peled SJones MRahul S(2021)Active-Learning a Convex Body in Low DimensionsAlgorithmica10.1007/s00453-021-00807-w83:6(1885-1917)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00453-021-00807-w

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents