Thumbnail
Access Restriction
Open

Author Orai, Wael El ♦ Schmitt, Dominique
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Convex Inclusion Chain ♦ Planar Point Set ♦ Convex Hull ♦ Simple Polygonal Line ♦ Order-k Voronoi Di-agram ♦ Efficient On-line Algorithm ♦ Distinct K-sets ♦ New Number ♦ Chosen Convex Inclusion Chain
Abstract Abstract. Given a set V of n points in the plane, we introduce a new number of k-sets that is an invariant of V: the number of k-sets of a convex inclusion chain of V. A convex inclusion chain of V is an order-ing (v1, v2,..., vn) of the points of V such that no point of the ordering belongs to the convex hull of its predecessors. The k-sets of such a chain are then the distinct k-sets of all the subsets {v1,..., vi}, for all i in {k + 1,..., n}. We show that the number of these k-sets depends only on V and not on the chosen convex inclusion chain. Moreover, this number is surprisingly equal to the number of regions of the order-k Voronoi di-agram of V. As an application, we give an efficient on-line algorithm to compute the k-sets of the vertices of a simple polygonal line, no vertex of which belonging to the convex hull of its predecessors on the line. 1
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article