Parametric search: three new applications

Abstract

Parametric search is a useful tool in geometric optimization. Invented by Nimrod Megiddo in 1983, it has been widely used in computational geometry. Unfortunately, this technique has rarely been used in the combinatorial optimization community in China. In this paper, we introduce parametric search via three new geometric optimization applications.

Keywords

Parametric search / geometric optimization / facility location

References

[1] Agarwal P, Bereg S, Daescu O, Kaplan H, Ntafos S, Sharir M, Zhu B. Guarding a terrain by two watchtowers. Algorithmica (to appear)

[2] Agarwal P, Bereg S, Daescu O, Kaplan H, Ntafos S, Zhu B. Guarding a terrain by two watchtowers. In: Proc 21st Annu Sympos Comput Geom. 2005, 346–355

[3] Agarwal P, Sharir M, Toledo S. Applications of parametric searching in geometric optimization. In: Proceedings of the 3rd Annual ACM-SIAM Sympos on Discrete Algo (SODA’92). 1992, 72–82

[4] Agarwal P., Sharir M., Welzl E. The discrete 2-center problem. Discrete Comput Geom, 1998, 20: 287-305.

[5] Atallah M. J., Chen D. Z., Wagner H. An optimal parallel algorithm for the visibility of a simple polygon from a point. J ACM, 1991, 38(3): 516-533.

[6] Ben-Moshe B, Katz M J, Mitchell J S B. A constant-factor approximation algorithm for optimal terrain guarding. In: Proc 16th Annu ACM-SIAM Sympos Discrete Algo. 2005, 515–524

[7] Bespamyatnikh S, Chen Z, Wang K, Zhu B. On the planar two-watchtower problem. In: Proc 7th Annu Internat Conf Computing and Combinatorics. 2001, 121–130

[8] Chan T. More planar two-center algorithms. Comput Geom Theory Appls, 1999, 13: 189-198.

[9] Clarkson K, Varadarajan K. Improved approximation algorithms for geometric set cover. In: Proc 21st Annu Sympos Comput Geom. 2005, 135–141

[10] Cole R. Slowing down sorting networks to obtain faster sorting algorithms. J ACM, 1987, 34: 200-208.

[11] Cole R., Sharir M. Visibility problems for polyhedral terrains. J Symbolic Comput, 1989, 7: 11-30.

[12] ElGindy H., Avis D. A linear time algorithm for computing the visibility polygon from a point. J Algorithms, 1981, 2(4): 186-197.

[13] Eppstein D. Faster construction of planar two-centers. In: Proc 8th Annu ACM-SIAM Sympos Discrete Algo. 1997, 131–138

[14] Guibas L., Hershberger J., Leven D., Sharir M., Tarjan R. Linear time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica, 1987, 2(2): 209-234.

[15] Halperin D, Sharir M, Goldberg A. The 2-center problem with obstacles. In: Proc 16th Annu Sympos Comput Geom, 2000, 80–90

[16] Joe B. On the correction of a linear time visibility polygon algorithm. Intl J Comput Math, 1990, 32: 155-172.

[17] Joe B., Simpson R. B. Correction to Lee’s visibility polygon algorithm. BIT, 1987, 27: 458-473.

[18] Ko M. T., Lee R. C. T., Chang J. S. An optimal approximation algorithm for the rectilinear m-center problem. Algorithmica, 1990, 5: 341-352.

[19] Lee D. T. Visibility of a simple polygon. Comput Vision Graph Image Process, 1983, 22: 207-221.

[20] Megiddo N. Applying parallel computation algorithms in the design of serial algorithms. J ACM, 1983, 30: 852-865.

[21] Nilsson B. Guarding Art Galleries: Methods for Mobile Guards. Doctoral Thesis. Dept Comput Sci, Lund University, 1994

[22] van Oostrum R, Veltkamp R. Parametric search made practical. In: Proc 18th Annu Sympos Comput Geom. 2002, 1–9

[23] O’Rourke J. Art Gallery Theorems and Algorithms, 1987, Oxford: Oxford University Press.

[24] Preparata F. P., Shamos M. I. Computational Geometry: An Introduction, 1985, Berlin: Springer-Verlag.

[25] Sharir M. A near-linear algorithm for the planar 2-center problem. Discrete Comput Geom, 1997, 4: 125-134.

[26] Sharir M., Agarwal P. K. Davenport Schinzel Sequences and Their Geometric Applications, 1995, New York: Cambridge University Press.

[27] Shin C -S, Kim J -H, Kim S -K, Chwa K -Y. Two-center problems for a convex polygon. In: Proc 6th European Sympos Algorithms (ESA’98). 1998, 199–210

[28] Zhu B. Computing the shortest watchtower of a polyhedral terrain in O(n log n) time. Comput Geom Theory Appls, 1997, 8: 181-193.