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. |

Remarks: |

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