Diameter, width, closest line pair, and parametric searching
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1993. Diameter, width, closest line pair, and parametric searching. Discrete & Computational Geometry. 10(1), 183–196.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA 
;
Guibas, Leonidas;
Sharir, Micha
;
Guibas, Leonidas;
Sharir, MichaAbstract
We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic.
Publishing Year
Date Published
1993-12-01
Journal Title
Discrete & Computational Geometry
Publisher
Springer
Acknowledgement
*Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.
Volume
10
Issue
1
Page
183 - 196
ISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Diameter, width, closest line pair, and parametric searching. Discrete & Computational Geometry. 1993;10(1):183-196. doi:10.1007/BF02573973
Chazelle, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1993). Diameter, width, closest line pair, and parametric searching. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02573973
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “Diameter, Width, Closest Line Pair, and Parametric Searching.” Discrete & Computational Geometry. Springer, 1993. https://doi.org/10.1007/BF02573973.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Diameter, width, closest line pair, and parametric searching,” Discrete & Computational Geometry, vol. 10, no. 1. Springer, pp. 183–196, 1993.
Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1993. Diameter, width, closest line pair, and parametric searching. Discrete & Computational Geometry. 10(1), 183–196.
Chazelle, Bernard, et al. “Diameter, Width, Closest Line Pair, and Parametric Searching.” Discrete & Computational Geometry, vol. 10, no. 1, Springer, 1993, pp. 183–96, doi:10.1007/BF02573973.
Link(s) to Main File(s)
Access Level
Closed Access
Google Scholar