|
Gift wrapping algorithm - Definition and Overview |
| Related Words: Algorism, Attack, Course, Fashion, Figures, Form, Guise, Line, Lines, Math, Mathematic, Mathematics, Means, Method, Methodology |
|
|
|
The gift wrapping algorithm is a simple algorithm for computing the convex hull of a given set of points.
Planar case
In the two-dimensional case the algorithm is also known as Jarvis march, by the name of the author, and has O(NK) time complexity, where N is the number of points and K is the number of points on the convex hull. Its real-life performance compared with other convex hull algorithms is favorable when N is small or K is expected to be very small with respect to N. In general case the algorithm is outperformed by many others.
The gift wrapping algorithm begins with a point A known to be on the convex hull, e.g., the leftmost point, and selects the point B such that all points are to the right of the line AB. This point may be found on O(N) time by comparing polar angles of all points with respect to point A taken for the center of polar coordinates. Repeating with B and so on until one reaches A again yields the convex hull in K steps. The gift wrapping algorithm is exactly analogous to the process of winding a string (or wrapping paper) around the set of points.
Higher dimensions
The approach is extendable to higher dimensions.
Related articles
|
Example Usage of algorithm |
 |
Mkissler: My love for the Skins exceeds the Hate for them Cowboys.....trust me the algorithm proves it. Philthy doesn't deserve a algorithm. |
 |
qu5h: "The News Feed uses an algorithm to display the stories FB thinks are most interesting to u.subset of all stories u could possibly see. |
 |
unknownix: The New Google Caffeine Search algorithm http://bte.tc/Mq8 #RTW |
|
|
