Convex Hulls

Abstract:

An object is convex if any two points inside it can be connected via a straight line that is entirely inside the object. This chapter opens with a discussion of convexity and then defines the convex hull: The tightest fitting convex region of space that covers a given object. Initially, several algorithms for computing 2D convex hulls are considered and then methods for 3D convex hulls. In particular, we discuss an incremental algorithm where one adds a triangle at a time and the divide and conquer approach where the object is recursively divided until the computations are trivial. The essential part of the divide and conquer approach is to recursively merge the convex hulls of the parts.

Año de publicación:

2012

Keywords:

Fuente:

google