Document Open Access Logo

Economical Delone Sets for Approximating Convex Bodies

Authors Ahmed Abdelkader , David M. Mount

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2018.4.pdf
  • Filesize: 0.66 MB
  • 12 pages

Document Identifiers

Author Details

Ahmed Abdelkader
  • Department of Computer Science , University of Maryland, College Park MD, USA
David M. Mount
  • Department of Computer Science and Institute of Advanced Computer Studies , University of Maryland, College Park MD, USA

Funding

Research supported by NSF grant CCF–1618866.

Cite As Get BibTex

Ahmed Abdelkader and David M. Mount. Economical Delone Sets for Approximating Convex Bodies. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 4:1-4:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SWAT.2018.4

Abstract

Convex bodies are ubiquitous in computational geometry and optimization theory. The high combinatorial complexity of multidimensional convex polytopes has motivated the development of algorithms and data structures for approximate representations. This paper demonstrates an intriguing connection between convex approximation and the classical concept of Delone sets from the theory of metric spaces. It shows that with the help of a classical structure from convexity theory, called a Macbeath region, it is possible to construct an epsilon-approximation of any convex body as the union of O(1/epsilon^{(d-1)/2}) ellipsoids, where the center points of these ellipsoids form a Delone set in the Hilbert metric associated with the convex body. Furthermore, a hierarchy of such approximations yields a data structure that answers epsilon-approximate polytope membership queries in O(log (1/epsilon)) time. This matches the best asymptotic results for this problem, by a data structure that both is simpler and arguably more elegant.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Approximate polytope membership
  • Macbeath regions
  • Delone sets
  • Hilbert geometry

Metrics

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

References

  1. P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. J. Assoc. Comput. Mach., 51:606-635, 2004. Google Scholar
  2. S. Arya, G. D. da Fonseca, and D. M. Mount. Approximate polytope membership queries. In Proc. 43rd Annu. ACM Sympos. Theory Comput., pages 579-586, 2011. Google Scholar
  3. S. Arya, G. D. da Fonseca, and D. M. Mount. Polytope approximation and the Mahler volume. In Proc. 23rd Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 29-42, 2012. Google Scholar
  4. S. Arya, G. D. da Fonseca, and D. M. Mount. Approximate polytope membership queries. SIAM J. Comput., 2017. To appear. Google Scholar
  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-–10:15, 2017. Google Scholar
  6. S. Arya, G. D. da Fonseca, and D. M. Mount. On the combinatorial complexity of approximating polytopes. Discrete & Computational Geometry, 58(4):849-870, 2017. Google Scholar
  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. Google Scholar
  8. 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
  9. I. Bárány. The technique of M-regions and cap-coverings: A survey. Rend. Circ. Mat. Palermo, 65:21-38, 2000. Google Scholar
  10. I. Bárány and D. G. Larman. Convex bodies, economic cap coverings, random polytopes. Mathematika, 35:274-291, 1988. Google Scholar
  11. J. L. Bentley, M. G. Faust, and F. P. Preparata. Approximation algorithms for convex hulls. Commun. ACM, 25(1):64-68, 1982. Google Scholar
  12. A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In Proc. 23rd Internat. Conf. on Machine Learning, pages 97-104, 2006. Google Scholar
  13. H. Brönnimann, B. Chazelle, and J. Pach. How hard is halfspace range searching. Discrete Comput. Geom., 10:143-155, 1993. Google Scholar
  14. C. J. C. Burges. A tutorial on support vector machines for pattern recognition. Data Min. Knowl. Discov., 2(2):121-167, 1998. Google Scholar
  15. T. M. Chan. Fixed-dimensional linear programming queries made easy. In Proc. 12th Annu. Sympos. Comput. Geom., pages 284-290, 1996. Google Scholar
  16. T. M. Chan. Output-sensitive results on convex hulls, extreme points, and related problems. Discrete Comput. Geom., 16:369-387, 1996. Google Scholar
  17. B. Chazelle and J. Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. J. Algorithms, 21:579-597, 1996. Google Scholar
  18. K. L. Clarkson. An algorithm for approximate closest-point queries. In Proc. Tenth Annu. Sympos. Comput. Geom., pages 160-164, 1994. Google Scholar
  19. K. L. Clarkson. Building triangulations using ε-nets. In Proc. 38th Annu. ACM Sympos. Theory Comput., pages 326-335, 2006. Google Scholar
  20. R. M. Dudley. Metric entropy of some classes of sets with differentiable boundaries. J. Approx. Theory, 10(3):227-236, 1974. Google Scholar
  21. J. Erickson, L. J. Guibas, J. Stolfi, and L. Zhang. Separation-sensitive collision detection for convex objects. In Proc. Tenth Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 327-336, 1999. Google Scholar
  22. G. Ewald, D. G. Larman, and C. A. Rogers. The directions of the line segments and of the r-dimensional balls on the boundary of a convex body in Euclidean space. Mathematika, 17:1-20, 1970. 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 and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. SIAM J. Comput., 35:1148-1184, 2006. Google Scholar
  25. D. Hilbert. Ueber die gerade linie als kürzeste verbindung zweier punkte. Mathematische Annalen, 46:91-96, 1895. Google Scholar
  26. 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
  27. A. M. Macbeath. A theorem on non-homogeneous lattices. Ann. of Math., 56:269-293, 1952. Google Scholar
  28. J. Matoušek and O. Schwarzkopf. On ray shooting in convex polytopes. Discrete Comput. Geom., 10:215-232, 1993. Google Scholar
  29. J. Matoušek. Reporting points in halfspaces. Comput. Geom. Theory Appl., 2:169-186, 1992. Google Scholar
  30. J. Matoušek. Linear optimization queries. J. Algorithms, 14(3):432-448, 1993. Google Scholar
  31. F. Nielsen and L. Shao. On Balls in a Hilbert Polygonal Geometry (Multimedia Contribution). In Proc. 33rd Internat. Sympos. Comput. Geom., pages 67:1-67:4, 2017. Google Scholar
  32. A. Papadopoulos and M. Troyanov. Handbook of Hilbert Geometry. European Mathematical Society, 2014. Google Scholar
  33. E. A. Ramos. Linear programming queries revisited. In Proc. 16th Annu. Sympos. Comput. Geom., pages 176-181, 2000. Google Scholar
  34. C. Vernicos and C. Walsh. Flag-approximability of convex bodies and volume growth of Hilbert geometries. HAL Archive (hal-01423693i), 2016. URL: https://hal.archives-ouvertes.fr/hal-01423693.
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