The Weber Point can be Found in Linear Time for Points in Biangular Configuration
Authors: Luzi Anderegg, Mark Cieliebak, and Giuseppe Prencipe
Reference: Technical Report TR-03-01, Universitá di Pisa, Dipartimento di Informatica, January 2003
Download: Postscript (.ps) or PDF (.pdf)
Abstract: The Weber point of a given point set P is a point in the plane that minimizes the sum of all distances to the points in P. In general, the Weber point cannot be computed. However, if the points are in specific geometric patterns, then finding the Weber point is possible. We investigate the case of {biangular configurations}, where there is a center and two angles $\alpha$ and $\beta$ such that the angles w.r.t. the center between each two adjacent points is either $\alpha$ or $\beta$, and these angles alternate. We show that in this case the center of biangularity is the Weber point of the points, and that it can be found in time linear in the number of points.

Note: electronic versions may not always correspond exactly to printed versions.