Report
A Note on the 2-Colored Rectilinear Crossing Number of Random Point Sets in the Unit Square
| العنوان: | A Note on the 2-Colored Rectilinear Crossing Number of Random Point Sets in the Unit Square |
|---|---|
| المؤلفون: | Cabello, Sergio, Czabarka, Éva, Fabila-Monroy, Ruy, Higashikawa, Yuya, Seidel, Raimund, Székely, László, Tkadlec, Josef, Wesolek, Alexandra |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, Computer Science - Computational Geometry |
| الوصف: | Let $S$ be a set of four points chosen independently, uniformly at random from a square. Join every pair of points of $S$ with a straight line segment. Color these edges red if they have positive slope and blue, otherwise. We show that the probability that $S$ defines a pair of crossing edges of the same color is equal to $1/4$. This is connected to a recent result of Aichholzer et al. [GD 2019] who showed that by 2-colouring the edges of a geometric graph and counting monochromatic crossings instead of crossings, the number of crossings can be more than halfed. Our result shows that for the described random drawings, there is a coloring of the edges such that the number of monochromatic crossings is in expectation $\frac{1}{2}-\frac{7}{50}$ of the total number of crossings. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2312.01935 |
| رقم الانضمام: | edsarx.2312.01935 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |