pipette
ENEnglish

Larger Crossing Families

Joachim Orthaber, Patrick Schnider

Preprint

En palabras de los autores

We give the first explicit constant for crossing families of linear size by showing that every set of points in general position in the plane contains a crossing family of size approximately . We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.