Diameter (computational Geometry)
In computational geometry, the diameter of a finite set of points or of a polygon is its diameter as a set, the largest distance between any two points. The diameter is always attained by two points of the convex hull of the input. A trivial brute-force search can be used to find the diameter of n points in time O(n^2) (assuming constant-time distance evaluations) but faster algorithms are possible for points in low dimensions. Static 2d input In two dimensions, the diameter can be obtained by computing the convex hull and then applying the method of rotating calipers. This involves finding two parallel support lines for the convex hull (for instance vertical lines through the two vertices with minimum and maximum x-coordinate) and then rotating the two lines through a sequence of discrete steps that keep them as parallel lines of support until they have rotated back to their original orientation. The diameter is the maximum distance between any pair of convex hull vertices ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]