Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications. (Q2704992)

In this paper several continuous 1-facility center problems with respect to a given \(n\) vertex simple polygon \(P\) are discussed. The objective is to find a point which minimizes the maximum distance to all points in \(P\). It is discussed that the problem can be reduced to minimize only the maximum distance to all vertices of \(P\). First algorithms for finding the constrained Euclidean centre are described. \(O(n \log n + k)\) algorithms (where \(k\) is the number of intersections between \(P\) and the furthest point Voronoi diagram of the vertices of \(P\)) to find the centre constrained to \(P\) or to the boundary of \(P\) are derived.NEWLINENEWLINEIn the next part of the paper the constrained geodesic centre is looked at. The geodesic distance between two points in \(P\) is the length of a shortest path connecting the two points inside \(P\). It is shown that the geodesic centre with respect to the boundary of \(P\) can be computed in \(O(n \log n)\) and the geodesic centre with respect to \(P\) can be computed in \(O(n(n + k))\), where here \(k\) is the number of intersections between \(P\) and the furthest point geodesic Voronoi diagram.NEWLINENEWLINEIn the last part of the paper the link centre of \(P\) is investigated. The link distance counts the number of breakpoints in a shortest path between to points inside \(P\). The link centre with respect to the boundary of \(P\) can be computed in \(O(n \log n)\) time.NEWLINENEWLINEAs an application the problem of finding a suitable location for the pin gate is given. The pin gate is the point from which liquid is poured or injected into a mold. Here the maximum distance from the pin gate to any point in the object should be small and the maximum number of turns the liquid takes on its path from the pin gate to any point in the object should also be small.NEWLINENEWLINEThe paper gives some nice insights in the tight relation between location theory and computational geometry.