Document Open Access Logo

On the Complexity of Closest Pair via Polar-Pair of Point-Sets

Authors Roee David, Karthik C. S., Bundit Laekhanukit

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.28.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Roee David
Karthik C. S.
Bundit Laekhanukit

Cite AsGet BibTex

Roee David, Karthik C. S., and Bundit Laekhanukit. On the Complexity of Closest Pair via Polar-Pair of Point-Sets. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.28

Abstract

Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Delta is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact dimension of the complete bipartite graph K_{n,n} in various L^p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.
Keywords
  • Contact dimension
  • Sphericity
  • Closest Pair
  • Fine-Grained Complexity

Metrics

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

References

  1. Amir Abboud, Aviad Rubinstein, and R. Ryan Williams. Distributed PCP theorems for hardness of approximation in P. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 25-36, 2017. URL: http://dx.doi.org/10.1109/FOCS.2017.12.
  2. Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed PCP theorems for hardness of approximation in P. CoRR, abs/1706.06407, 2017. Preliminary version in FOCS'17. URL: http://arxiv.org/abs/1706.06407,
  3. Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 136-150, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.18.
  4. Noga Alon and Pavel Pudlák. Equilateral sets in 𝓁_pⁿ. Geometric & Functional Analysis GAFA, 13(3):467-482, 2003. URL: http://dx.doi.org/10.1007/s00039-003-0418-7.
  5. Hans-Jürgen Bandelt, Victor Chepoi, and Monique Laurent. Embedding into rectilinear spaces. Discrete & Computational Geometry, 19(4):595-604, 1998. URL: http://dx.doi.org/10.1007/PL00009370.
  6. Michael Ben-Or. Lower bounds for algebraic computation trees (preliminary report). In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 80-86, 1983. URL: http://dx.doi.org/10.1145/800061.808735.
  7. Jon Louis Bentley. Multidimensional divide-and-conquer. Commun. ACM, 23(4):214-229, 1980. URL: http://dx.doi.org/10.1145/358841.358850.
  8. Jon Louis Bentley and Michael Ian Shamos. Divide-and-conquer in multidimensional space. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing, May 3-5, 1976, Hershey, Pennsylvania, USA, pages 220-230, 1976. URL: http://dx.doi.org/10.1145/800113.803652.
  9. Yonatan Bilu and Nathan Linial. Monotone maps, sphericity and bounded second eigenvalue. J. Comb. Theory, Ser. B, 95(2):283-299, 2005. URL: http://dx.doi.org/10.1016/j.jctb.2005.04.005.
  10. Michel Deza and Hiroshi Maehara. A few applications of negative- type inequalities. Graphs and Combinatorics, 10(2-4):255-262, 1994. URL: http://dx.doi.org/10.1007/BF02986674.
  11. Peter Frankl and Hiroshi Maehara. On the contact dimensions of graphs. Discrete & Computational Geometry, 3:89-96, 1988. URL: http://dx.doi.org/10.1007/BF02187899.
  12. Omer Gold and Micha Sharir. Dominance products and faster algorithms for high-dimensional closest pair under dollarl_backslashinftydollar. CoRR, abs/1605.08107, 2016. URL: http://arxiv.org/abs/1605.08107,
  13. Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, New York, NY, USA, 1 edition, 2008. Google Scholar
  14. Richard K Guy. An olla-podrida of open problems, often oddly posed. The American Mathematical Monthly, 90(3):196-200, 1983. Google Scholar
  15. Klaus H. Hinrichs, Jürg Nievergelt, and Peter Schorn. Plane-sweep solves the closest pair problem elegantly. Inf. Process. Lett., 26(5):255-261, 1988. URL: http://dx.doi.org/10.1016/0020-0190(88)90150-0.
  16. Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, and Ely Porat. Closest pair problems in very high dimensions. In Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings, pages 782-792, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27836-8_66.
  17. William B Johnson and Joram Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26(189-206):1, 1984. Google Scholar
  18. Jørn Justesen. Class of constructive asymptotically good algebraic codes. IEEE Trans. Information Theory, 18(5):652-656, 1972. URL: http://dx.doi.org/10.1109/TIT.1972.1054893.
  19. Samir Khuller and Yossi Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34-37, 1995. URL: http://dx.doi.org/10.1006/inco.1995.1049.
  20. Jack H. Koolen, Monique Laurent, and Alexander Schrijver. Equilateral dimension of the rectilinear space. Des. Codes Cryptography, 21(1/3):149-164, 2000. Google Scholar
  21. Hiroshi Maehara. Space graphs and sphericity. Discrete Applied Mathematics, 7(1):55-64, 1984. Google Scholar
  22. Hiroshi Maehara. Contact patterns of equal nonoverlapping spheres. Graphs and Combinatorics, 1(1):271-282, 1985. URL: http://dx.doi.org/10.1007/BF02582952.
  23. Hiroshi Maehara. Dispersed points and geometric embedding of complete bipartite graphs. Discrete & Computational Geometry, 6:57-67, 1991. URL: http://dx.doi.org/10.1007/BF02574674.
  24. Michael O. Rabin. Probabilistic algorithms. In Proceedings of a Symposium on New Directions and Recent Results in Algorithms and Complexity, Computer Science Department, Carnegie-Mellon University, April 7-9, 1976, pages 21-39, 1976. Google Scholar
  25. Fred S Roberts. On the boxicity and cubicity of a graph. Recent Progresses in Combinatorics, pages 301-310, 1969. Google Scholar
  26. Aviad Rubinstein. Hardness of approximate nearest neighbor search. CoRR, abs/1803.00904, 2018. URL: http://arxiv.org/abs/1803.00904.
  27. Michael Ian Shamos and Dan Hoey. Closest-point problems. In 16th Annual Symposium on Foundations of Computer Science, Berkeley, California, USA, October 13-15, 1975, pages 151-162, 1975. URL: http://dx.doi.org/10.1109/SFCS.1975.8.
  28. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. CoRR, abs/1011.3027, 2010. URL: http://arxiv.org/abs/1011.3027,
  29. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. Preliminary version in ICALP'04. URL: http://dx.doi.org/10.1016/j.tcs.2005.09.023.
  30. Ryan Williams. On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity in computational geometry. arXiv preprint arXiv:1709.05282, 2017. Google Scholar
  31. Virginia Vassilevska Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16-18, 2015, Patras, Greece, pages 17-29, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.17.
  32. Virginia Vassilevska Williams. Fine-grained algorithms and complexity (invited talk). In 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, pages 3:1-3:1, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.3.
  33. Andrew Chi-Chih Yao. Lower bounds for algebraic computation trees with integer inputs. SIAM J. Comput., 20(4):655-668, 1991. Preliminary version in FOCS'89. URL: http://dx.doi.org/10.1137/0220041.
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