--- res: bibo_abstract: - 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.@eng bibo_authorlist: - foaf_Person: foaf_givenName: Bernard foaf_name: Chazelle, Bernard foaf_surname: Chazelle - foaf_Person: foaf_givenName: Herbert foaf_name: Edelsbrunner, Herbert foaf_surname: Edelsbrunner foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87 orcid: 0000-0002-9823-6833 - foaf_Person: foaf_givenName: Leonidas foaf_name: Guibas, Leonidas foaf_surname: Guibas - foaf_Person: foaf_givenName: Micha foaf_name: Sharir, Micha foaf_surname: Sharir bibo_doi: 10.1007/BF02573973 bibo_issue: '1' bibo_volume: 10 dct_date: 1993^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/0179-5376 dct_language: eng dct_publisher: Springer@ dct_title: Diameter, width, closest line pair, and parametric searching@ ...