Advertisement
Published in:
2006 | OriginalPaper | Chapter
k-Sets of Convex Inclusion Chains of Planar Point Sets
Authors : Wael El Oraiby, Dominique Schmitt
Published in: Mathematical Foundations of Computer Science 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 ordering (
v
1
,
v
2
, ...,
v
n
) 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 {
v
1
, ...,
v
i
}, 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 diagram 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.