Computation of Convex Hulls
In computational geometry, a number of algorithms are known for computing the convex hull for a finite set of points and for other geometric objects.
Computing the convex hull means constructing an unambiguous, efficient representation of the required convex shape. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.
For points in two and three dimensions, output-sensitive algorithms are known that compute the convex hull in time O(n log h). For dimensions d higher than 3, the time for computing the convex hull is, matching the worst-case output complexity of the problem.
Read more about this topic: Convex Hull
Famous quotes containing the words computation of, computation and/or hulls:
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“I suppose that Paderewski can play superbly, if not quite at his best, while his thoughts wander to the other end of the world, or possibly busy themselves with a computation of the receipts as he gazes out across the auditorium. I know a great actor, a master technician, can let his thoughts play truant from the scene ...”
—Minnie Maddern Fiske (1865–1932)
“To anybody who can hold the Present at its worth without being inappreciative of the Past, it may be forgiven, if to such an one the solitary old hulk at Portsmouth, Nelson’s Victory, seems to float there, not alone as the decaying monument of a fame incorruptible, but also as a poetic approach, softened by its picturesqueness, to the Monitors and yet mightier hulls of the European ironclads.”
—Herman Melville (1819–1891)