Colored ray configurations

DOI10.1016/J.COMGEO.2017.05.008MaRDI QIDQ1699300zbMATH OpenOpenAlexFDO

Authors R. Fabila-Monroy, Ferran Hurtado, Rafel Jaume, P. Pérez-Lantero, Maria Saumell, Rodrigo I. Silveira, J. Urrutia, Alfredo García, Javier Tejel

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.03415, http://hdl.handle.net/2117/122154

zbMATH Keywords

enumerative problemscircular sequencescolored raysray configurationsred and blue points in the plane

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: 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 $Theta(n^2)$ 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.

Recommendations

• Configurations of non-crossing rays and related problems
• On the number of radial orderings of planar point sets.
• On the number of radial orderings of colored planar point sets
• Geometric spanning cycles in bichromatic point sets
• On determining non-isotopic configurations of points on a circle

Cites work

• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• scientific article; zbMATH DE number 2209732 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Bounds on the maximum multiplicity of some common geometric graphs
• Configurations of non-crossing rays and related problems
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Counting triangulations of planar point sets
• Extremal combinatorics. With applications in computer science
• On orthogonal ray graphs
• On the Number of Crossing‐Free Matchings, Cycles, and Partitions
• On the number of plane geometric graphs
• On the recognition of four-directional orthogonal ray graphs
• Simple alternating path problem
• The clique problem in ray intersection graphs

This page was built for publication: Colored ray configurations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699300)