英和和英

出典:『Wikipedia』 (2011/05/25 07:45 UTC 版)

英語による解説

引用

In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2 or 3 dimensional space. The algorithm takes O(n log h) time, where h is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an O(n log n) algorithm (Graham scan, for example) with Jarvis march, in order to obtain an optimal O(n log h) time. Chan's algorithm is notable because it is much simpler than the ultimate planar convex hull algorithm, and it naturally extends to 3-dimensional space.