Faster Algorithms for Computing Plurality Points

Authors Mark de Berg, Joachim Gudmundsson, Mehran Mehr



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.32.pdf
  • Filesize: 0.51 MB
  • 15 pages

Document Identifiers

Author Details

Mark de Berg
Joachim Gudmundsson
Mehran Mehr

Cite AsGet BibTex

Mark de Berg, Joachim Gudmundsson, and Mehran Mehr. Faster Algorithms for Computing Plurality Points. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.SoCG.2016.32

Abstract

Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,p'). A point p is called a plurality point if it is preferred by at least as many voters as any other point p'. We present an algorithm that decides in O(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector <w_1(v), ...,w_d(v)> and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).
Keywords
  • computational geometry
  • computational social choice
  • voting theory
  • plurality points
  • Condorcet points

Metrics

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

References

  1. H. K. Ahn, S. W. Cheng, O. Cheong, M. Golin, and R. van Oostrum. Competitive facility location: the Voronoi game. Theor. Comput. Sci., 310(1-3):457-467, 2004. Google Scholar
  2. T. Chan. An optimal randomized algorithm for maximum tukey depth. In Proc. 15th ACM-SIAM Symp. Discr. Alg. (SODA), pages 430-436, 2004. Google Scholar
  3. B. Chazelle. On the convex layers of a planar set. IEEE Trans. Inf. Theory, 31(4):509-517, 1985. Google Scholar
  4. O. Cheong, S. Har-Peled, N. Linial, and J. Matousek. The one-round voronoi game. Discr. Comput. Geom., 31(1):125-138, 2004. Google Scholar
  5. H. Edelsbrunner, J. O’Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications. SIAM J. Comput., 15(2):341-363, 1986. Google Scholar
  6. H. A. Eiselt and G. Laporte. Sequential location problems. Europ. J. Op. Res., 96(2):217-231, 1997. Google Scholar
  7. J. Erickson. New lower bounds for convex hull problems in odd dimensions. SIAM J. Comput., 28(4):1198-1214, 1999. Google Scholar
  8. A. Gajentaan and M. H. Overmars. On a class of o(n²) problems in computational geometry. Comput. Geom. Theory Appl., 5(3):165-185, 1995. Google Scholar
  9. T. Gallai. Solution to problem number 4065. The American Mathematical Monthly, 51(3):169-171, 1944. Google Scholar
  10. P. Hansen and J. F. Thisse. Outcomes of voting and planning: Condorcet, weber and rawls locations. Journal of Public Economics, 16(1):1-15, 1981. Google Scholar
  11. P. Hansen, J. F. Thisse, and R. E. Wendell. Equivalence of solutions to network location problems. Mathematics of Operations Research, 11(4):672-678, 1986. Google Scholar
  12. S. Jadhav, A. Mukhopadhyay, and B. Bhattacharya. An optimal algorithm for the intersection radius of a set of convex polygons. J. Alg., 20(2):244-267, 1996. Google Scholar
  13. D. Kress and E. Pesch. Sequential competitive location on networks. Europ. J. Op. Res., 217(3):483-499, 2012. Google Scholar
  14. W. Y. Lin, Y. W. Wu, H. L. Wang, and K. M. Chao. Forming plurality at minimum cost. In Proc. 9th Int. Workshop Alg. Comput. (WALCOM), LNCS 8973, pages 77-88, 2015. Google Scholar
  15. R. D. McKelvey and R. E. .Wendell. Voting equilibria in multidimensional choice spaces. Math. Op. Res., 1(2):144-158, 1976. Google Scholar
  16. J. W. Tukey. Mathematics and the picturing of data. In In Proc. Int. Cong. Mathematicians, volume 2, pages 523-531, 1975. Google Scholar
  17. R. E. Wendell and R. D. McKelvey. New perspectives in competitive location theory. Europ. J. Op. Res., 6(2):174-182, 1981. Google Scholar
  18. R. E. Wendell and S. J. Thorson. Some generalizations of social decisions under majority rule. Econometrica, 42(5):893-912, 1974. Google Scholar
  19. Y. W. Wu, W. Y. Lin, H. L. Wang, and K. M. Chao. Computing plurality points and condorcet points in euclidean space. In Proc. 24th Int. Symp. Alg. Comput. (ISAAC), LNCS 8283, pages 688-698, 2013. 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