On the number of radial orderings of planar point sets.
José Miguel Díaz-Báñez, Ruy Fabila-Monroy, Pablo Pérez-Lantero
Abstract
Given a set S of n points in the plane, a
radial ordering of S with respect to a point
p (not in S) is a clockwise circular
ordering of the elements in S by angle around
p. If S is two-colored, a colored
radial ordering is a radial ordering of S in which
only the colors of the points are considered. In this paper, we
obtain bounds on the number of distinct non-colored and colored
radial orderings of S. We assume a strong general
position on S, not three points are collinear and not
three lines 14;each passing through a pair of points in
S 14;intersect in a point of
ℝ2 \ S. In the colored
case, S is a set of 2n points partitioned
into n red and n blue points, and
n is even. We prove that: the number of distinct radial
orderings of S is at most O(n4)
and at least Ω(n3); the number of
colored radial orderings of S is at most
O(n4) and at least Ω(n);
there exist sets of points with Θ(n4)
colored radial orderings and sets of points with only
O(n2) colored radial orderings.
Full Text: PDF PostScript