k-Sets of Convex Inclusion Chains of Planar Point Sets

摘要: Given a set V of n points in the plane, we introduce new number k-sets that is an invariant V: convex inclusion chain V. A ordering (v1, v2, ..., vn) such no point belongs to hull its predecessors. The are then distinct all subsets {v1, vi}, for i {k+1, n}. We show these depends only on and not chosen chain. Moreover, this surprisingly equal regions order-k Voronoi diagram As application, give efficient on-line algorithm compute vertices simple polygonal line, vertex which belonging predecessors line.