Result: Colored ray configurations

Title:
Colored ray configurations
Authors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. CGA - Computational Geometry and Applications, Fabila Monroy, Ruy, Garcia Olaverri, Alfredo Martin, Hurtado Díaz, Fernando Alfredo, Jaume, Rafel, Pérez Lantero, Pablo, Saumell, Maria, Silveira, Rodrigo Ignacio, Tejel Altarriba, Francisco Javier, Urrutia Galicia, Jorge
Publisher Information:
2018-05
Document Type:
Electronic Resource Electronic Resource
Index Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica, Àrees temàtiques de la UPC::Matemàtiques i estadística, Numerical analysis, Computing Methodologies, Ray configurations, Red and blue points in the plane, Colored rays, Circular sequences, Enumerative problems, Anàlisi numèrica, Informàtica, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Classificació AMS::68 Computer science::68U Computing methodologies and applications, Article
URL:
http://hdl.handle.net/2117/122154
http://www.sciencedirect.com/science/article/pii/S092577211730041X
Availability:
Open access content. Open access content
Open Access
Note:
17 p.
application/pdf
English
Other Numbers:
HGF oai:upcommons.upc.edu:2117/122154
Fabila, R., Garcia, A., Hurtado, F., Jaume, R., Pérez, P., Saumell, M., Silveira, R.I., Tejel, F., URRUTIA, J. Colored ray configurations. "Computational geometry: theory and applications", Maig 2018, vol. 68, p. 292-308.
0925-7721
10.1016/j.comgeo.2017.05.008
1073026423
Contributing Source:
UNIV POLITECNICA DE CATALUNYA
From OAIster®, provided by the OCLC Cooperative.
Accession Number:
edsoai.on1073026423
Database:
OAIster

Further Information

© 2018. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0
We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be T(n2) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set.
Peer Reviewed
Postprint (author's final draft)