On the number of radial orderings of planar point sets

Details On the number of radial orderings of planar point sets On the number of radial orderings of planar point sets

2012-04-02

arxiv.org/abs/1204.0547v1

Computer Science

Computational Geometry

Scientific paper

Given a set $S$ of $n$ points in the plane, a \emph{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 \emph{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---each passing through a pair of points in $S$---intersect in a point of $\R^2\setminus 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(n^4)$ and at least $\Omega(n^3)$; the number of colored radial orderings of $S$ is at most $O(n^4)$ and at least $\Omega(n)$; there exist sets of points with $\Theta(n^4)$ colored radial orderings and sets of points with only $O(n^2)$ colored radial orderings.

Affiliated with

Also associated with

No associations

Rating

On the number of radial orderings of planar point sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the number of radial orderings of planar point sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the number of radial orderings of planar point sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-354009