Document Open Access Logo

Approximate Nearest-Neighbor Search for Line Segments

Authors Ahmed Abdelkader , David M. Mount

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.4.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Ahmed Abdelkader
  • Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin, TX, USA
David M. Mount
  • Department of Computer Science and Institute of Advanced Computer Studies, University of Maryland, College Park, MD, USA

Funding

Supported by NSF grant CCF-1618866 and an Ann G. Wylie Dissertation Fellowship.

Acknowledgements

The first author’s work was conducted in part at the University of Maryland.

Cite As Get BibTex

Ahmed Abdelkader and David M. Mount. Approximate Nearest-Neighbor Search for Line Segments. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.4

Abstract

Approximate nearest-neighbor search is a fundamental algorithmic problem that continues to inspire study due its essential role in numerous contexts. In contrast to most prior work, which has focused on point sets, we consider nearest-neighbor queries against a set of line segments in ℝ^d, for constant dimension d. Given a set S of n disjoint line segments in ℝ^d and an error parameter ε > 0, the objective is to build a data structure such that for any query point q, it is possible to return a line segment whose Euclidean distance from q is at most (1+ε) times the distance from q to its nearest line segment. We present a data structure for this problem with storage O((n²/ε^d) log (Δ/ε)) and query time O(log (max(n,Δ)/ε)), where Δ is the spread of the set of segments S. Our approach is based on a covering of space by anisotropic elements, which align themselves according to the orientations of nearby segments.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Approximate nearest-neighbor searching
  • Approximate Voronoi diagrams
  • Line segments
  • Macbeath regions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. A. Abdelkader and D. M. Mount. Economical Delone sets for approximating convex bodies. In Proc. 16th Scand. Workshop Algorithm Theory, pages 4:1-4:12, 2018. Google Scholar
  2. P. K. Agarwal, N. Rubin, and M. Sharir. Approximate nearest neighbor search amid higher-dimensional flats. In Proc. 25th Annu. European Sympos. Algorithms, volume 87, pages 4:1-4:13, 2017. Google Scholar
  3. O. Aichholzer, D. Z. Chen, D. T. Lee, A. Mukhopadhyay, E. Papadopoulou, and F. Aurenhammer. Voronoi diagrams for direction-sensitive distances. In Proc. 13th Annu. Sympos. Comput. Geom., pages 418-420, 1997. Google Scholar
  4. A. Andoni, P. Indyk, R. Krauthgamer, and H. L. Nguyên. Approximate line nearest neighbor in high dimensions. In Proc. 20th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 293-301, 2009. Google Scholar
  5. A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten. Hölder homeomorphisms and approximate nearest neighbors. In Proc. 59th Annu. IEEE Sympos. Found. Comput. Sci., pages 159-169, 2018. Google Scholar
  6. Boris Aronov. A lower bound on Voronoi diagram complexity. Inform. Process. Lett., 83(4):183-185, 2002. Google Scholar
  7. S. Arya, G. D. da Fonseca, and D. M. Mount. Near-optimal ε-kernel construction and related problems. In Proc. 33rd Internat. Sympos. Comput. Geom., pages 10:1-15, 2017. URL: http://arxiv.org/abs/1604.01175.
  8. S. Arya, G. D. da Fonseca, and D. M. Mount. On the combinatorial complexity of approximating polytopes. Discrete Comput. Geom., 58(4):849-870, 2017. URL: http://dx.doi.org/10.1007/s00454-016-9856-5.
  9. S. Arya, G. D. da Fonseca, and D. M. Mount. Optimal approximate polytope membership. In Proc. 28th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 270-288, 2017. Google Scholar
  10. S. Arya, G. D. da Fonseca, and D. M. Mount. Approximate convex intersection detection with applications to width and Minkowski sums. In Proc. 26th Annu. European Sympos. Algorithms, pages 3:1-14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.3.
  11. S. Arya, G. D. da Fonseca, and D. M. Mount. Approximate polytope membership queries. SIAM J. Comput., 47(1):1-51, 2018. URL: http://dx.doi.org/10.1137/16M1061096.
  12. S. Arya and T. Malamatos. Linear-size approximate Voronoi diagrams. In Proc. 13th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 147-155, 2002. Google Scholar
  13. S. Arya, T. Malamatos, and D. M. Mount. Space-time tradeoffs for approximate nearest neighbor searching. J. Assoc. Comput. Mach., 57:1-54, 2009. URL: http://dx.doi.org/10.1145/1613676.1613677.
  14. F. Aurenhammer, B. Jüttler, and G. Paulini. Voronoi Diagrams for Parallel Halflines and Line Segments in Space. In Proc. 28th Annu. Internat. Sympos. Algorithms Comput., volume 92, pages 7:1-7:10, 2017. Google Scholar
  15. I. Bárány. The technique of M-regions and cap-coverings: A survey. Rend. Circ. Mat. Palermo, 65:21-38, 2000. Google Scholar
  16. G. Barequet, E. Papadopoulou, and M. Suderland. Unbounded Regions of High-Order Voronoi Diagrams of Lines and Segments in Higher Dimensions. In Proc. 30th Annu. Internat. Sympos. Algorithms Comput., volume 149, pages 62:1-62:15, 2019. Google Scholar
  17. R. Basri, T. Hassner, and L. Zelnik-Manor. Approximate nearest subspace search. IEEE Trans. Pattern Anal. Mach. Intell., 33:266-278, 2011. Google Scholar
  18. J.-D. Boissonnat, M. Sharir, B. Tagansky, and M. Yvinec. Voronoi diagrams in higher dimensions under certain polyhedral distance functions. Discrete Comput. Geom., 19(4):485-519, April 1998. Google Scholar
  19. B. Chazelle, D. Liu, and A. Magen. Approximate range searching in higher dimension. Comput. Geom. Theory Appl., 39:24-29, 2008. Google Scholar
  20. L.P. Chew, K. Kedem, M. Sharir, B. Tagansky, and E. Welzl. Voronoi diagrams of lines in 3-space under polyhedral convex distance functions. J. Algorithms, 29(2):238-255, 1998. Google Scholar
  21. S. Cost and S. Salzberg. A weighted nearest neighbor algorithm for learning with symbolic features. Machine Learning, 10:57-78, 1993. Google Scholar
  22. T. M. Cover and P. E. Hart. Nearest neighbor pattern classification. IEEE Trans. Image Proc., 13:57-67, 1967. Google Scholar
  23. S. Deerwester, S. T. Dumals, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis. J. Amer. Soc. Inform. Sci., 41:391-407, 1990. Google Scholar
  24. L. Devroye and T. J. Wagner. Nearest neighbor methods in discrimination. In P. R. Krishnaiah and L. N. Kanal, editors, Handbook of Statistics, volume 2. North-Holland, 1982. Google Scholar
  25. R. O. Duda and P. E. Hart. Pattern Classification and Scene Analysis. John Wiley & Sons, NY, 1973. Google Scholar
  26. I. Z. Emiris, T. Malamatos, and E. Tsigaridas. Approximate nearest neighbor queries among parallel segments. In 26th European Workshop on Computational Geometry (EuroCG 2010), 2010. Google Scholar
  27. H. Everett, D. Lazard, S. Lazard, and M. Safey El Din. The Voronoi diagram of three lines. Discrete Comput. Geom., 42(1):94-130, July 2009. Google Scholar
  28. U. M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy. Advances in Knowledge Discovery and Data Mining. AAAI Press/Mit Press, 1996. Google Scholar
  29. M. Flickner, H. Sawhney, W. Niblack, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: The QBIC system. IEEE Computer, 28:23-32, 1995. Google Scholar
  30. A. Gersho and R. M. Gray. Vector Quantization and Signal Compression. Kluwer Academic, Boston, MA, 1991. Google Scholar
  31. S. Har-Peled. A replacement for Voronoi diagrams of near linear size. In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., pages 94-103, 2001. Google Scholar
  32. S. Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theo. of Comput., 8:321-350, 2012. Google Scholar
  33. S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput., 35:1148-1184, 2006. Google Scholar
  34. P. Indyk. Nearest neighbors in high-dimensional spaces. In J. E. Goodman and J. O'Rourke, editors, The Handbook of Discrete and Computational Geometry, 2nd Edition, pages 877-892. Chapman & Hall/CRC, Boca Raton, FL, 2004. Google Scholar
  35. F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, pages 187-204. Interscience Publishers, Inc., New York, 1948. Google Scholar
  36. M. I. Karavelas. A robust and efficient implementation for the segment Voronoi diagram. In Internat. Symp. on Voronoi Diagrams in Sci. and Engin., volume 2004, pages 51-62, 2004. Google Scholar
  37. V. Koltun and M. Sharir. 3-dimensional Euclidean Voronoi diagrams of lines with a fixed number of orientations. SIAM J. Comput., 32(3):616-642, 2003. Google Scholar
  38. V. Koltun and M. Sharir. Polyhedral Voronoi diagrams of polyhedra in three dimensions. Discrete Comput. Geom., 31(1):83-124, January 2004. Google Scholar
  39. R. Krauthgamer and J. R. Lee. Navigating nets: Simple algorithms for proximity search. In Proc. 15th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 798-807, 2004. Google Scholar
  40. R. Krauthgamer and J. R. Lee. The black-box complexity of nearest-neighbor search. Theo. Comp. Sci., 348:262-276, 2005. Google Scholar
  41. A. Laddha, Y. T. Lee, and S. Vempala. Strong self-concordance and sampling. In Proc. 52nd Annu. ACM Sympos. Theory Comput., pages 1212-1222, 2020. Google Scholar
  42. A. M. Macbeath. A compactness theorem for affine equivalence-classes of convex regions. Canad. J. Math, 3:54-61, 1950. Google Scholar
  43. S. Mahabadi. Approximate nearest line search in high dimensions. In Proc. 26th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 337-354, 2015. Google Scholar
  44. W. Mulzer, H. L. Nguyên, P. Seiferth, and Y. Stein. Approximate k-flat nearest neighbor search. In Proc. 47th Annu. ACM Sympos. Theory Comput., pages 783-792, 2015. Google Scholar
  45. H. Narayanan. Randomized interior point methods for sampling and optimization. Ann. Appl. Probab., 26(1):597-641, 2016. Google Scholar
  46. Y. Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Springer Publishing Company, Incorporated, 2014. Google Scholar
  47. Y. Nesterov and M. Todd. On the Riemannian geometry defined by self-concordant barriers and interior-point methods. Found. Comput. Math., 2(4):333-361, 2002. Google Scholar
  48. S. Sachdeva and N. K. Vishnoi. The mixing time of the Dikin walk in a polytope - A simple proof. Oper. Res. Lett., 44(5):630-634, 2016. Google Scholar
  49. K. Sugihara and M. Iri. A robust topology-oriented incremental algorithm for Voronoi diagrams. Internat. J. Comput. Geom. Appl., 04:179-228, 1994. Google Scholar
  50. S. Vijayanarasimhan, P. Jain, and K. Grauman. Hashing hyperplane queries to near points with applications to large-scale active learning. IEEE Trans. Pattern Anal. Mach. Intell., 36:276-288, 2014. Google Scholar
  51. X. Wang, S. Atev, J. Wright, and G. Lerman. Fast subspace search via Grassmannian based hashing. In Proc. IEEE Internat. Conf. Comput. Vision (ICCV), December 2013. Google Scholar
  52. S. J. Wright. Primal-Dual Interior-Point Methods. Society for Industrial and Applied Mathematics, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact