Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications
Prosenjit K. Bose, Godfried Toussaint · 2002
In the manufacturing industry, finding a suitable location for the pin gate (the point from which liquid is poured or injected into a mould) is a difficult problem when viewed from the fluid dynamics of the moulding process. However, experience has shown that a suitable pin gate location possesses several geometric characteristics: the distance from the pin gate to any point in the mould should be small, and the number of turns on the path from a point in the mould to the pin gate should be small. We address the problem of computing locations that possess these geometric characteristics. Given a mould M (modelled by an n-vertex simple polygon), we show how to compute the Euclidean centre of M, when it is constrained to lie in the interior of M or on the boundary of M, in O(n log n + k) time, where k is the number of intersections between M and the furthest-point Voronoi diagram of the vertices of M. We show how to compute the geodesic centre of M, when it is constrained to the boundary, in O(n log n) time, and the geodesic centre of M, when it is constrained to lie in a polygonal region, in O[n(n+k)] time. Finally, we show how to compute the link centre of M, when it is constrained to the boundary of M, in O(n log n) time.