Document Open Access Logo

Fast Algorithms for Geometric Consensuses

Authors Sariel Har-Peled, Mitchell Jones

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.50.pdf
  • Filesize: 3.51 MB
  • 16 pages

Document Identifiers

Author Details

Sariel Har-Peled
  • Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA
Mitchell Jones
  • Dept. of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA

Funding

  • Har-Peled, Sariel: Supported in part by NSF AF award CCF-1907400.
  • Jones, Mitchell: Supported in part by NSF AF award CCF-1907400.

Acknowledgements

The authors thank Joachim Gudmundsson for bringing the problem of computing the yolk to our attention. The second author thanks Sampson Wong for discussions on computing the yolk in higher dimensions. We also thank Timothy Chan for useful comments (in particular, the improved algorithm for the yolk in 3D, see Remark 26).

Cite AsGet BibTex

Sariel Har-Peled and Mitchell Jones. Fast Algorithms for Geometric Consensuses. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 50:1-50:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.50

Abstract

Let P be a set of n points in ℝ^d in general position. A median hyperplane (roughly) splits the point set P in half. The yolk of P is the ball of smallest radius intersecting all median hyperplanes of P. The egg of P is the ball of smallest radius intersecting all hyperplanes which contain exactly d points of P. We present exact algorithms for computing the yolk and the egg of a point set, both running in expected time O(n^(d-1) log n). The running time of the new algorithm is a polynomial time improvement over existing algorithms. We also present algorithms for several related problems, such as computing the Tukey and center balls of a point set, among others.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Geometric optimization
  • centerpoint
  • voting games

Metrics

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

Related Versions

References

  1. Boris Aronov, Marco Pellegrini, and Micha Sharir. On the zone of a surface in a hyperplane arrangement. Discrete Comp. Geom., 9:177-186, 1993. URL: https://doi.org/10.1007/BF02189317.
  2. Binay K. Bhattacharya, Shreesh Jadhav, Asish Mukhopadhyay, and Jean-Marc Robert. Optimal algorithms for some intersection radius problems. Computing, 52(3):269-279, 1994. URL: https://doi.org/10.1007/BF02246508.
  3. Duncan Black. On the rationale of group decision-making. Journal of Political Economy, 56(1):23-34, 1948. URL: https://doi.org/10.1086/256633.
  4. Timothy M. Chan. An optimal randomized algorithm for maximum Tukey depth. In J. Ian Munro, editor, Proc. 15th ACM-SIAM Sympos. Discrete Algs. (SODA), pages 430-436. SIAM, 2004. URL: http://dl.acm.org/citation.cfm?id=982792.982853.
  5. Timothy M. Chan and Konstantinos Tsakalidis. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete Comp. Geom., 56(4):866-881, 2016. URL: https://doi.org/10.1007/s00454-016-9784-4.
  6. Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete Comp. Geom., 9:145-158, 1993. URL: https://doi.org/10.1007/BF02189314.
  7. Kenneth L. Clarkson. Las vegas algorithms for linear and integer programming when the dimension is small. J. ACM, 42(2):488-499, 1995. URL: https://doi.org/10.1145/201019.201036.
  8. Mark de Berg, Jonathan Chung, and Joachim Gudmundsson. Computing the yolk in spatial voting games, 2019. Google Scholar
  9. Mark de Berg, Katrin Dobrindt, and Otfried Schwarzkopf. On lazy randomized incremental construction. Discrete Comp. Geom., 14(3):261-286, 1995. URL: https://doi.org/10.1007/BF02570705.
  10. Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. Faster algorithms for computing plurality points. ACM Trans. Algorithms, 14(3):36:1-36:23, 2018. URL: https://doi.org/10.1145/3186990.
  11. Herbert Edelsbrunner, Raimund Seidel, and Micha Sharir. On the zone theorem for hyperplane arrangements. SIAM J. Comput., 22(2):418-429, 1993. URL: https://doi.org/10.1137/0222031.
  12. Joachim Gudmundsson and Sampson Wong. Computing the yolk in spatial voting games without computing median lines. In 33th Conf. Artificial Intell. (AAAI), 2019. Google Scholar
  13. Joachim Gudmundsson and Sampson Wong. Computing the yolk in spatial voting games without computing median lines. CoRR, abs/1902.04735, 2019. URL: http://arxiv.org/abs/1902.04735.
  14. Sariel Har-Peled and Mitchell Jones. Fast algorithms for geometric consensuses. CoRR, abs/1912.01639, 2019. URL: http://arxiv.org/abs/1912.01639.
  15. Jiří Matoušek. Reporting points in halfspaces. Comput. Geom., 2:169-186, 1992. URL: https://doi.org/10.1016/0925-7721(92)90006-E.
  16. Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Grad. Text in Math. Springer, 2002. URL: https://doi.org/10.1007/978-1-4613-0039-7/.
  17. Richard D. McKelvey. Covering, dominance, and institution-free properties of social choice. American Journal of Political Science, 30(2):283-314, 1986. URL: https://doi.org/10.2307/2111098.
  18. Ariel Rubinstein. A note about the "nowhere denseness" of societies having an equilibrium under majority rule. Econometrica, 47(2):511-514, 1979. URL: https://doi.org/10.2307/1914198.
  19. Raimund Seidel. Small-dimensional linear programming and convex hulls made easy. Discrete Comp. Geom., 6:423-434, 1991. URL: https://doi.org/10.1007/BF02574699.
  20. Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems. In 9th Symp. on Theoretical Aspects of Comput. Sci. (STACS), pages 569-579, 1992. URL: https://doi.org/10.1007/3-540-55210-3_213.
  21. Richard E. Stone and Craig A. Tovey. Limiting median lines do not suffice to determine the yolk. Social Choice and Welfare, 9(1):33-35, 1992. URL: https://doi.org/10.1007/BF00177668.
  22. Craig A. Tovey. A polynomial-time algorithm for computing the yolk in fixed dimension. Math. Program., 57:259-277, 1992. URL: https://doi.org/10.1007/BF01581084.
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