Computing a double-ray center for a planar point set

Authors
Glozman, A Kedem, K Shpitalnik, G
Citation
A. Glozman et al., Computing a double-ray center for a planar point set, INT J C GEO, 9(2), 1999, pp. 109-123
Citations number
17
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS
ISSN journal
02181959 → ACNP
Volume
9
Issue
2
Year of publication
1999
Pages
109 - 123
Database
ISI
SICI code
0218-1959(199904)9:2<109:CADCFA>2.0.ZU;2-7
Abstract
A double-ray configuration is a configuration in the plane consisting of tw o rays emanating from one point. Given a set S of n points in the plane, we want to find a double-ray configuration that minimizes the Hausdorff dista nce from S to this configuration. We call this problem the double-ray cente r problem. We present an efficient algorithm for computing the double-ray c enter for set S of n points in the plane which runs in time O(n(3)alpha(n) log(2)n).