Document Open Access Logo

Assigning Weights to Minimize the Covering Radius in the Plane

Authors Eunjin Oh, Hee-Kap Ahn

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2016.58.pdf
  • Filesize: 451 kB
  • 12 pages

Document Identifiers

Subject Classification

Keywords
  • Weighted center
  • facility location
  • weight assignment
  • combinatorial op- timization
  • computational geometry

Metrics

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

Abstract

Given a set P of n points in the plane and a multiset W of k weights with k leq n, we assign a weight in W to a point in P to minimize the maximum weighted distance from the weighted center of P to any point in P. In this paper, we give two algorithms which take O(k^2 n^2 log^4 n) time and O(k^5 n log^4 k + kn log^3 n) time, respectively. For a constant k, the second algorithm takes only O(n log^3 n) time, which is near-linear.

Cite As Get BibTex

Eunjin Oh and Hee-Kap Ahn. Assigning Weights to Minimize the Covering Radius in the Plane. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 58:1-58:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ISAAC.2016.58

Author Details

Eunjin Oh
Hee-Kap Ahn

References

  1. Pankaj K. Agarwal, Mark de Berg, Jiří Matousěk, and Otfried Schwarzkopf. Constructing levels in arrangements and higher order voronoi diagrams. SIAM Journal on Computing, 27(3):654-667, 1998. Google Scholar
  2. Pankaj K. Agarwal and Micha Sharir. Computer Science Today: Recent Trends and Developments, chapter Algorithmic techniques for geometric optimization, pages 234-253. Springer Berlin Heidelberg, Berlin, Heidelberg, 1995. Google Scholar
  3. Behrooz Alizadeh and Rainer E. Burkard. The inverse 1-center location problem on a tree. Technical Report 2009-03, Graz University of Technology, 2009. Google Scholar
  4. Luis Barba, Otfried Cheong, Jean-Lou De Carufel, Michael Gene Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot, and Tianhao Wang. Weight balancing on boundaries and skeletons. In Proceedings of the Thirtieth Annual Symposium on Computational Geometry (SoCG 2014), pages 436-443, 2014. Google Scholar
  5. Oded Berman, Divinagracia I. Ingco, and Amedeo Odoni. Improving the location of minimax facilities through network modification. Networks, 24(1):31-41, 1994. Google Scholar
  6. Mao-Cheong Cai, X. G. Yang, and J. Z. Zhang. The complexity analysis of the inverse center location problem. Journal of Global Optimization, 15(2):213-218, 1999. Google Scholar
  7. Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770-785, 1988. Google Scholar
  8. Martin Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM Journal on Computing, 13(1):31-45, 1984. Google Scholar
  9. Der-Tsai Lee. On k-nearest neighbor voronoi diagrams in the plane. IEEE Trans. Computers, 31(6):478-487, 1982. Google Scholar
  10. Nimrod Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, 1983. Google Scholar
  11. Nimrod Megiddo. Linear-time algorithms for linear programming in ℝ³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. Google Scholar
  12. Nimrod Megiddo. Linear programming in linear time when the dimension is fixed. Journal of the ACM, 31(1):114-127, 1984. Google Scholar
  13. Nimrod Megiddo. On the ball spanned by balls. Discrete &Computational Geometry, 4(6):605-610, 1989. Google Scholar
  14. Edgar A. Ramos. On range reporting, ray shooting and k-level construction. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (SoCG 1999), pages 390-399, 1999. Google Scholar
  15. Jianzhong Zhang, Zhenhong Liu, and Zhongfan Ma. Some reverse location problems. European Journal of Operational Research, 124(1):77-88, 2000. 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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact