| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
OK, I have searched for all occurances of "convex hull" in here and
have not found an answer to this question: How fast can we find the
convex hull of a set of points in the 2-D plane?
Or for those not familiar with terminology:
Given a set of points in the X-Y plane, determine the shortest list
of points that completely encloses the set.
How fast can this be done?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1148.1 | N log N | ALLVAX::ROTH | If you plant ice you'll harvest wind | Mon Nov 06 1989 06:28 | 16 |
It can be done in O(N log N) time in general - it's primarily a sorting
problem. You only require O(N) space for this.
There are a number of algorithms available - for example it's easier
if the points are vertices of a simple polygon but harder if you need to
incrementally keep the convex hull as more points are added.
There are at least two books to look thru for more information:
Algorithms in Combinatorial Geometry,
H. Edelsbrunner, Springer
Computational Geometry, an Introduction
F. Preperata & M. Shamos, Springer
- Jim
| |||||