HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

On the numbers of radial orderings of planar point sets

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01188901
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Monday, August 31, 2015 - 5:03:11 PM
Last modification on : Wednesday, October 16, 2019 - 2:48:40 PM
Long-term archiving on: : Tuesday, December 1, 2015 - 10:41:53 AM

File

dmtcs-16-3-17.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

José Miguel Dıaz-Banez, Ruy Fabila-Monroy, Pablo Pérez-Lantero. On the numbers of radial orderings of planar point sets. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (3), pp.291--304. ⟨10.46298/dmtcs.2087⟩. ⟨hal-01188901⟩

Share

Metrics

Record views

37

Files downloads

731