On the Fermat-Weber Point of a Polygonal Chain and its Generalizations

DOI10.3233/FI-2011-406zbMATH Open1255.68186arXiv1004.2958MaRDI QIDQ2895768

Bhaswar B. Bhattacharya

Publication date: 4 July 2012

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Abstract: In this paper, 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(leqn)$ 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 $ngeqN(k)$. We also show that $lceilpim(m+1)-p{i}^2/4ceilleqN(k)leqlfloorpim(m+1)+1floor$, 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(hklogk)$ time algorithm for determining whether a given set of $k$ points, having $h$ points on the convex hull, belongs to such a family.

Full work available at URL: https://arxiv.org/abs/1004.2958

zbMATH Keywords

optimizationfacility locationcomputational geometrypolygonsFermat-Weber problem

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Discrete location and assignment (90B80)

Related Items (1)

Title not available (Why is that?)

This page was built for publication: On the Fermat-Weber Point of a Polygonal Chain and its Generalizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2895768)