Dıaz-Banez, José Miguel and Fabila-Monroy, Ruy and Pérez-Lantero, Pablo - On the numbers of radial orderings of planar point sets

dmtcs:2087 - Discrete Mathematics & Theoretical Computer Science, December 16, 2014, Vol. 16 no. 3 (in progress)
On the numbers of radial orderings of planar point sets

Authors: Dıaz-Banez, José Miguel and Fabila-Monroy, Ruy and Pérez-Lantero, Pablo

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.


Source : oai:HAL:hal-01188901v1
Volume: Vol. 16 no. 3 (in progress)
Section: Combinatorics
Published on: December 16, 2014
Submitted on: April 16, 2012
Keywords: radial orderings,colored point sets,star polygonizations,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 17 times.
This article's PDF has been downloaded 71 times.