Document Open Access Logo

Smooth Distance Approximation

Authors Ahmed Abdelkader , David M. Mount

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.5.pdf
  • Filesize: 1.11 MB
  • 18 pages

Document Identifiers

Author Details

Ahmed Abdelkader
  • Google LLC, Mountain View, CA, USA
David M. Mount
  • Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA

Acknowledgements

Conducted in part while the first author was a postdoctoral fellow at the University of Texas at Austin, and completed before he joined Google LLC.

Cite As Get BibTex

Ahmed Abdelkader and David M. Mount. Smooth Distance Approximation. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ESA.2023.5

Abstract

Traditional problems in computational geometry involve aspects that are both discrete and continuous. One such example is nearest-neighbor searching, where the input is discrete, but the result depends on distances, which vary continuously. In many real-world applications of geometric data structures, it is assumed that query results are continuous, free of jump discontinuities. This is at odds with many modern data structures in computational geometry, which employ approximations to achieve efficiency, but these approximations often suffer from discontinuities. 
In this paper, we present a general method for transforming an approximate but discontinuous data structure into one that produces a smooth approximation, while matching the asymptotic space efficiencies of the original. We achieve this by adapting an approach called the partition-of-unity method, which smoothly blends multiple local approximations into a single smooth global approximation.
We illustrate the use of this technique in a specific application of approximating the distance to the boundary of a convex polytope in ℝ^d from any point in its interior. We begin by developing a novel data structure that efficiently computes an absolute ε-approximation to this query in time O(log (1/ε)) using O(1/ε^{d/2}) storage space. Then, we proceed to apply the proposed partition-of-unity blending to guarantee the smoothness of the approximate distance field, establishing optimal asymptotic bounds on the norms of its gradient and Hessian.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Approximation algorithms
  • convexity
  • continuity
  • partition of unity

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. URL: https://doi.org/10.4230/LIPIcs.SWAT.2018.4.
  2. R. Al-Aifari, I. Daubechies, and Y. Lipman. Continuous procrustes distance between two surfaces. Commun. Pure and Appl. Math., 66:934-964, 2013. URL: https://doi.org/10.1002/cpa.21444.
  3. N. Amenta and M. Bern. Surface reconstruction by voronoi filtering. Discrete Comput. Geom., 22:481-504, 1999. URL: https://doi.org/10.1007/PL00009475.
  4. R. Arya, S. Arya, G. D. da Fonseca, and D. M. Mount. Optimal bound on the combinatorial complexity of approximating polytopes. ACM Trans. Algorithms, 18(4):1-29, 2022. URL: https://doi.org/10.1145/3559106.
  5. 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: https://doi.org/10.4230/LIPIcs.SoCG.2017.10.
  6. 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: https://doi.org/10.1007/s00454-016-9856-5.
  7. 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. URL: https://doi.org/10.1137/1.9781611974782.18.
  8. S. Arya, G. D. da Fonseca, and D. M. Mount. Economical convex coverings and applications. In Proc. 34th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 1834-1861, 2023. URL: https://doi.org/10.1137/1.9781611977554.ch70.
  9. S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Wu. An optimal algorithm for approximate nearest neighbor searching. J. Assoc. Comput. Mach., 45(6):891-923, 1998. URL: https://doi.org/10.1145/293347.293348.
  10. F. Aurenhammer, R. Klein, and D.-T. Lee. Voronoi Diagrams and Delaunay Triangulations. World Scientific Publishing Co., Inc., 1st edition, 2013. Google Scholar
  11. K. Ball. An elementary introduction to modern convex geometry. In S. Levy, editor, Flavors of Geometry, pages 1-58. Cambridge University Press, 1997. (MSRI Publications, Vol. 31). Google Scholar
  12. R. G. Bartle and D. R. Sherbert. Introduction to Real Analysis. Wiley, 3rd edition, 1999. Google Scholar
  13. J. Bloomenthal, C. Bajaj, J. Blinn, B. Wyvill, M.-P. Cani, A. Rockwood, and G. Wyvill. Introduction to Implicit Surfaces. Morgan Kaufmann, 1997. Google Scholar
  14. T. Brochu, E. Edwards, and R. Bridson. Efficient geometrically exact continuous collision detection. ACM Trans. Graph., 31(4):96:1-96:7, 2012. URL: https://doi.org/10.1145/2185520.2185592.
  15. B. Chazelle and J. Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms, 21:579-597, 1996. URL: https://doi.org/10.1006/jagm.1996.0060.
  16. J. Chibane, A. Mir, and G. Pons-Moll. Neural unsigned distance fields for implicit function learning. In Proc. 34th Internat. Conf. Neural Inf. Proc. Syst., 2020. URL: https://doi.org/10.48550/arXiv.2010.13938.
  17. T. Culver, J. Keyser, and D. Manocha. Accurate computation of the medial axis of a polyhedron. In Proc. Fifth ACM Symp. Solid Modeling and Applications, SMA '99, pages 179-190, 1999. URL: https://doi.org/10.1145/304012.304030.
  18. H. Edelsbrunner and J. Harer. Computational topology: An introduction. American Mathematical Soc., 2010. Google Scholar
  19. D. Eppstein and J. Erickson. Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions. In Proc. 14th Annu. Sympos. Comput. Geom., pages 58-67, 1998. URL: https://doi.org/10.1145/276884.276891.
  20. S. Fridovich-Keil, A. Yu, M. Tancik, Q. Chen, B. Recht, and A. Kanazawa. Plenoxels: Radiance fields without neural networks. In Proc. IEEE/CVF Conf. Comput. Vis. Patt. Recog. (CVPR), pages 5501-5510, 2022. URL: https://doi.org/10.1109/CVPR52688.2022.00542.
  21. A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In Proc. 25th International Conference on Very Large Data Bases, VLDB '99, pages 518-529, 1999. Google Scholar
  22. A. Gropp, L. Yariv, N. Haim, M. Atzmon, and Y. Lipman. Implicit geometric regularization for learning shapes. In Internat. Conf. Machine Learning, pages 3789-3799, 2020. Google Scholar
  23. 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
  24. 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
  25. S. Har-Peled and N. Kumar. Approximating minimization diagrams and generalized proximity search. SIAM J. Comput., 44:944-974, 2015. Google Scholar
  26. S. Har-Peled, N. Kumar, D. M. Mount, and B. Raichel. Space exploration via proximity search. Discrete Comput. Geom., 56:357-376, 2016. URL: https://doi.org/10.1007/s00454-016-9801-7.
  27. P. Kopp, E. Rank, V. M. Calo, and S. Kollmannsberger. Efficient multi-level hp-finite elements in arbitrary dimensions. Comput. Meth. Appl. Mech. Eng., 401, 2022. URL: https://doi.org/10.1016/j.cma.2022.115575.
  28. J. C. H. Lee, J. Li, C. Musco, J. M. Phillips, and W. M. Tai. Finding an approximate mode of a kernel density estimate. In Proc. 29th Annu. European Sympos. Algorithms, pages 61:1-61:19, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.61.
  29. J. M. Lee. Smooth Maps, pages 30-59. Springer New York, 2003. Google Scholar
  30. Y. Lipman. Phase transitions, distance functions, and implicit neural representations. In Proc. 38th Internat. Conf. Machine Learning, pages 6702-6712, 2021. Google Scholar
  31. R. Lopez-Padilla, R. Murrieta-Cid, and S. M. LaValle. Optimal gap navigation for a disc robot. In E. Frazzoli, T. Lozano-Perez, N. Roy, and D. Rus, editors, Algorithmic Foundations of Robotics X, pages 123-138, 2013. URL: https://doi.org/10.1007/978-3-642-36279-8_8.
  32. G. L. Marchetti, V. Polianskii, A. Varava, F. T. Pokorny, and D. Kragic. An efficient and continuous Voronoi density estimator. In Proc. 26th Internat. Conf. Artif. Intel. Stat., pages 4732-4744, 2023. URL: https://doi.org/10.48550/arXiv.2210.03964.
  33. P. McMullen. The maximum numbers of faces of a convex polytope. Mathematika, 17:179-184, 1970. Google Scholar
  34. J. M. Melenk and I. Babuška. The partition of unity finite element method: Basic theory and applications. Computer Methods in Applied Mechanics and Engineering, 139:289-314, 1996. Google Scholar
  35. Y. Ohtake, A. Belyaev, M. Alexa, G. Turk, and H.-P. Seidel. Multi-level partition of unity implicits. ACM Trans. Graph., 22:463-470, 2003. Google Scholar
  36. S. Osher and R. Fedkiw. Level Set Methods and Dynamic Implicit Surfaces. Springer New York, 2003. Google Scholar
  37. J. J. Park, P. Florence, J. Straub, R. Newcombe, and S. Lovegrove. Deepsdf: Learning continuous signed distance functions for shape representation. In Proc. IEEE/CVF Conf. Computer Vision and Pattern Recognition, pages 165-174, 2019. Google Scholar
  38. N. Sharp and A. Jacobson. Spelunking the deep: Guaranteed queries on general neural implicit surfaces via range analysis. ACM Trans. Graph., 41:1-16, 2022. URL: https://doi.org/10.1145/3528223.3530155.
  39. R. E. Showalter. Hilbert space methods in partial differential equations. Dover Publications, 2011. Google Scholar
  40. E. M. Stein. Singular Integrals and Differentiability Properties of Functions. Princeton Mathematical Series (PMS-30). Princeton University Press, 1970. URL: https://www.jstor.org/stable/j.ctt1bpmb07.
  41. A. Tagliasacchi, T. Delame, M. Spagnuolo, N. Amenta, and A. Telea. 3D Skeletons: A State-of-the-Art Report. Computer Graphics Forum, 35(2):573-597, 2016. URL: https://doi.org/10.1111/cgf.12865.
  42. K. Tiwari, B. Sakcak, P. Routray, Manivannan M., and S. M. LaValle. Visibility-inspired models of touch sensors for navigation. In IEEE/RSJ International Conference on Intelligent Robots and Systems, 2022. Google Scholar
  43. A. Vaxman, M. Campen, O. Diamanti, D. Panozzo, D. Bommes, K. Hildebrandt, and M. Ben-Chen. Directional field synthesis, design, and processing. In Computer Graphics Forum, volume 35, pages 545-572, 2016. Google Scholar
  44. V. J. Wei, R. C.-W. Wong, C. Long, D. M. Mount, and H. Samet. Proximity queries on terrain surface. ACM Trans. Database Syst., 47:1-59, 2022. URL: https://doi.org/10.1145/3563773.
  45. A. Yershova and S. M. LaValle. Improving motion-planning algorithms by efficient nearest-neighbor searching. IEEE Trans. Robotics, 23(1):151-157, 2007. Google Scholar
  46. N. Zander, H. Bériot, C. Hoff, P. Kodl, and L. Demkowicz. Anisotropic multi-level hp-refinement for quadrilateral and triangular meshes. Finite Elem. Anal. Design, 203, 2022. URL: https://doi.org/10.1016/j.finel.2021.103700.
  47. X. Zhang, Y. J. Kim, and D. Manocha. Continuous penetration depth. Computer-Aided Design, 46:3-13, 2014. 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