Approximate center points in dense point sets

✍ Scribed by Knut Verbarg

• Book ID: 104137355
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 618 KB
• Volume: 61
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(97)00017-3

✦ Synopsis

The notion of center points is one way to generalize the median of a finite ordered point set to higher dimensions.

A set P of n points in d-dimensional Euclidean space Ed is S-dense, if the ratio of the largest to the smallest distance between any two points of P is bounded by 6n'ld, with some constant S. We describe a simple, yet efficient algorithm to compute an approximate center point for a S-dense set P in time O(dn). The quality of the approximation depends on 6 and exponentially on the dimension d, where the absolute value of the exponent is in R(dlogd).

We also present an iteration method with a linear rate of convergence, which computes an improved l/( 2( d -1) (8 f 1 )d) -center point for sufficiently large n. @