Document Open Access Logo

Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry

Author Timothy M. Chan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.26.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Timothy M. Chan

Cite AsGet BibTex

Timothy M. Chan. Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.26

Abstract

We apply the polynomial method - specifically, Chebyshev polynomials - to obtain a number of new results on geometric approximation algorithms in low constant dimensions. For example, we give an algorithm for constructing epsilon-kernels (coresets for approximate width and approximate convex hull) in close to optimal time O(n + (1/epsilon)^{(d-1)/2}), up to a small near-(1/epsilon)^{3/2} factor, for any d-dimensional n-point set. We obtain an improved data structure for Euclidean *approximate nearest neighbor search* with close to O(n log n + (1/epsilon)^{d/4} n) preprocessing time and O((1/epsilon)^{d/4} log n) query time. We obtain improved approximation algorithms for discrete Voronoi diagrams, diameter, and bichromatic closest pair in the L_s-metric for any even integer constant s >= 2. The techniques are general and may have further applications.
Keywords
  • diameter
  • coresets
  • approximate nearest neighbor search
  • the polynomial method
  • streaming

Metrics

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

References

  1. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM, 51(4):606-635, 2004. Preliminary version in SODA'01 and FOCS'01. Google Scholar
  2. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Geometric approximation via coresets. In Emo Welzl, editor, Current Trends in Combinatorial and Computational Geometry, pages 1-30. Cambridge University Press, 2005. Google Scholar
  3. Pankaj K. Agarwal, Jirí Matoušek, and Subhash Suri. Farthest neighbors, maximum spanning trees and related problems in higher dimensions. Comput. Geom. Theory Appl., 1:189-201, 1991. URL: http://dx.doi.org/10.1016/0925-7721(92)90001-9.
  4. Josh Alman, Timothy M. Chan, and Ryan Williams. Polynomial representation of threshold functions and algorithmic applications. In Proc. 57th IEEE Symp. Found. Comput. Sci. (FOCS), pages 467-476, 2016. Google Scholar
  5. Alexandr Andoni and Huy L. Nguyen. Width of points in the streaming model. In Proc. 23rd ACM-SIAM Symp. Discrete Algorithms (SODA), pages 447-452, 2012. ACM Trans. Algorithms, to appear. Google Scholar
  6. S. Arya, G. D. da Fonseca, and D. M. Mount. Approximate polytope membership queries. In Proc. 43rd ACM Symp. Theory Comput. (STOC), pages 579-586, 2011. SIAM J. Comput., to appear. URL: http://www.uniriotec.br/~fonseca/polytope_conf.pdf, URL: http://dx.doi.org/10.1145/1993636.1993713.
  7. S. Arya, T. Malamatos, and D. M. Mount. Space-time tradeoffs for approximate nearest neighbor searching. J. ACM, 57:1-54, 2009. Preliminary version in SODA'02 and STOC'02. URL: http://dx.doi.org/10.1145/1613676.1613677.
  8. S. Arya, D. M. Mount, N. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM, 45:891-923, 1998. Preliminary version in SODA'94. Google Scholar
  9. Sunil Arya and Timothy M. Chan. Better ε-dependencies for offline approximate nearest neighbor search, Euclidean minimum spanning trees, and ε-kernels. In Proc. 30th Symp. Comput. Geom. (SoCG), pages 416-425, 2014. URL: http://dx.doi.org/10.1145/2582112.2582161.
  10. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal area-sensitive bounds for polytope approximation. In Proc. 28th Symp. Comput. Geom. (SoCG), pages 363-372, 2012. URL: http://dx.doi.org/10.1145/2261250.2261305.
  11. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. On the combinatorial complexity of approximating polytopes. In Proc. 32nd Symp. Comput. Geom. (SoCG), pages 11:1-11:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.11.
  12. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Near-optimal ε-kernel construction and related problems. In Proc. 33rd Symp. Comput. Geom. (SoCG), 2017. Google Scholar
  13. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. Optimal approximate polytope membership. In Proc. 28th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 270-288, 2017. Google Scholar
  14. Gill Barequet and Sariel Har-Peled. Efficiently approximating the minimum-volume bounding box of a point set in three dimensions. J. Algorithms, 38(1):91-109, 2001. Preliminary version in SODA'99. URL: http://dx.doi.org/10.1006/jagm.2000.1127.
  15. J. L. Bentley and J. B. Saxe. Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms, 1(4):301-358, 1980. Google Scholar
  16. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546-563, 2009. URL: http://dx.doi.org/10.1137/070683933.
  17. H. Breu, J. Gil, D. Kirkpatrick, and M. Werman. Linear time Euclidean distance transform algorithms. IEEE Trans. Pattern Analysis and Machine Intelligence, 17:529-533, 1995. Google Scholar
  18. Timothy M. Chan. Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus. Int. J. Comput. Geom.Appl., 12(1-2):67-85, 2002. Preliminary version in SoCG'00. URL: http://dx.doi.org/10.1142/S0218195902000748.
  19. Timothy M. Chan. Faster core-set constructions and data-stream algorithms in fixed dimensions. Comput. Geom. Theory Appl., 35(1-2):20-35, 2006. Preliminary version in SoCG'04. URL: http://dx.doi.org/10.1016/j.comgeo.2005.10.002.
  20. Timothy M. Chan. Dynamic streaming algorithms for ε-kernels. In Proc. 32nd Symp. Comput. Geom. (SoCG), pages 27:1-27:11, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.27.
  21. Timothy M. Chan and Ryan Williams. Deterministic APSP, orthogonal vectors, and more: Quickly derandomizing Razborov-Smolensky. In Proc. 27th ACM-SIAM Symp. Discrete Algorithms (SODA), pages 1246-1255, 2016. Google Scholar
  22. T. M. Chan. Approximate nearest neighbor queries revisited. Discrete Comput. Geom., 20:359-373, 1998. Preliminary version in SoCG'97. Google Scholar
  23. Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM J. Comput., 11(3):467-471, 1982. URL: http://dx.doi.org/10.1137/0211037.
  24. Sariel Har-Peled. A practical approach for computing the diameter of a point set. In Proc. 17th Symp. Comput. Geom. (SoCG), pages 177-186, 2001. URL: http://dx.doi.org/10.1145/378583.378662.
  25. Xiaohan Huang and Victor Y. Pan. Fast rectangular matrix multiplication and applications. J. Complexity, 14(2):257-299, 1998. URL: http://dx.doi.org/10.1006/jcom.1998.0476.
  26. R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. Google Scholar
  27. Otfried Schwarzkopf. Parallel computation of distance transforms. Algorithmica, 6(5):685-697, 1991. URL: http://dx.doi.org/10.1007/BF01759067.
  28. Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. J. ACM, 62(2):13, 2015. Preliminary version in FOCS'12. Google Scholar
  29. F. Yates. The design and analysis of factorial experiments. Technical Communication No. 35, Commonwealth Bureau of Soil Science, Harpenden, UK, 1937. Google Scholar
  30. H. Yu, P. K. Agarwal, R. Poreddy, and K. R. Varadarajan. Practical methods for shape fitting and kinetic data structures using coresets. Algorithmica, 52(3):378-402, 2008. Preliminary version in SoCG'04. Google Scholar
  31. Hamid Zarrabi-Zadeh. An almost space-optimal streaming algorithm for coresets in fixed dimensions. Algorithmica, 60(1):46-59, 2011. Preliminary version in ESA'08. URL: http://dx.doi.org/10.1007/s00453-010-9392-2.
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 Imprint Privacy Contact