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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2014, Vol. 16 no. 3 (in progress) (3), pp.291--304
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01188901
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 31 août 2015 - 17:03:11
Dernière modification le : jeudi 7 septembre 2017 - 01:03:42
Document(s) archivé(s) le : mardi 1 décembre 2015 - 10:41:53

Fichier

dmtcs-16-3-17.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01188901, version 1

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 (in progress) (3), pp.291--304. 〈hal-01188901〉

Partager

Métriques

Consultations de la notice

57

Téléchargements de fichiers

269