Abstract

Given a set SS of nn points in the plane, a \emph{radial ordering} of SS with respect to a point pp (not in SS) is a clockwise circular ordering of the elements in SS by angle around pp. If SS is two-colored, a \emph{colored radial ordering} is a radial ordering of SS 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 SS. We assume a strong general position on SS, not three points are collinear and not three lines---each passing through a pair of points in SS---intersect in a point of R2∖S\R^2\setminus S. In the colored case, SS is a set of 2n2n points partitioned into nn red and nn blue points, and nn is even. We prove that: the number of distinct radial orderings of SS is at most O(n4)O(n^4) and at least Ω(n3)Ω(n^3); the number of colored radial orderings of SS is at most O(n4)O(n^4) and at least Ω(n)Ω(n); there exist sets of points with Θ(n4)Θ(n^4) colored radial orderings and sets of points with only O(n2)O(n^2) colored radial orderings.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.