Minimum convex partition of a constrained point set

A convex partition with respect to a point set S is a planar subdivision wh ose vertices are the points of S, where the boundary of the unbounded outer face is the boundary of the convex hull of S, and every bounded interior f ace is a convex polygon. A minimum convex partition with respect to S is a convex partition of S such that the number of convex polygons is minimised. In this paper, we will present a polynomial time algorithm to find a minim um convex partition with respect to a point set S where S is constrained to lie on the boundaries of a fixed number of nested convex hulls. (C) 2001 E lsevier Science B.V. All rights reserved.