id: 06052759
dt: j
an: 06052759
au: Bhattacharya, Bhaswar B.
ti: On the Fermat-Weber point of a polygonal chain and its generalizations.
so: Fundam. Inform. 107, No. 4, 331-343 (2011).
py: 2011
pu: Polish Mathematical Society, Warsaw; IOS Press, Amsterdam
la: EN
cc: 
ut: computational geometry; facility location; Fermat-Weber problem;
    optimization; polygons
ci: 
li: doi:10.3233/FI-2011-406
ab: Summary: We study the properties of the Fermat-Weber point for a set of
    fixed points, whose arrangement coincides with the vertices of a
    regular polygonal chain. A k-chain of a regular n-gon is the segment of
    the boundary of the regular n-gon formed by a set of k ($\leq $ n)
    consecutive vertices of the regular n-gon. We show that for every odd
    positive integer k, there exists an integer $N(k)$, such that the
    Fermat-Weber point of a set of k fixed points lying on the vertices a
    k-chain of a n-gon coincides with a vertex of the chain whenever n
    $\geq N(k)$. We also show that é$πm(m + 1) - π^{2}/4$ù $\leq N(k)
    \leq $ ë$πm(m + 1) + 1$û, where k (= 2m + 1) is any odd positive
    integer. We then extend this result to a more general family of point
    set, and give an $O(hk \log k)$ time algorithm for determining whether
    a given set of k points, having h points on the convex hull, belongs to
    such a family.
rv: