Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications

Computing the constrained Euclidean, geodesic and link centre of a simple polygon with applications

0.00 Avg rating0 Votes
Article ID: iaor20012186
Country: Belgium
Volume: 15
Start Page Number: 37
End Page Number: 66
Publication Date: Dec 2000
Journal: Studies In Locational Analysis
Authors: ,
Abstract:

Given an n vertex simple polygon M, we show how to compute the Euclidean centre of M constrained to lie in the interior of M, in a polygonal region inside 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 constrained to the boundary in O(n log n) time and the geodesic centre of M constrained to lie in a polygonal region in O(n(n + k)) time where k is the number of intersections of the geodesic furthest point Voronoi diagram of M with the polygonal region. Furthermore, we show how to compute the link centre of M constrained to the boundary of M in O(n log n) time. Computing such locations has applications in such diverse fields as Geographic Information Systems (G.I.S.) and the manufacturing industry. The following problem was one of the main motives of this work. In the manufacturing industry, finding a suitable location for the pin gate (the pin gate is the point from which liquid is poured or injected into a mold) is a difficult problem when viewed from the fluid dynamics of the molding process. However, experience has shown that a suitable pin gate location possesses several desirable geometric characteristics, namely the distance from the pin gate to any point in the mold should be small and the number of turns on the path from a point in the mold to the pin gate should be small. The locations that possess these geometric characteristics are the constrained centres discussed above.

Reviews

Required fields are marked *. Your email address will not be published.