On crossing-families in planar point sets

DOI10.1016/J.COMGEO.2022.101899MaRDI QIDQ2144455zbMATH OpenOpenAlexWikidataFDO

Authors Jan Kynčl, Manfred Scheucher, Birgit Vogtenhuber, Oswin Aichholzer, Pavel Valtr

Publication date 13 June 2022

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2109.10705

zbMATH Keywords

order typepoint setcrossing familygeometric thrackle

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: A $k$-crossing family in a point set $S$ in general position is a set of $k$ segments spanned by points of $S$ such that all $k$ segments mutually cross. In this short note we present two statements on crossing families which are based on sets of small cardinality: (1) Any set of at least 15 points contains a crossing family of size 4. (2) There are sets of $n$ points which do not contain a crossing family of size larger than $8lceilfracn41ceil$. Both results improve the previously best known bounds.

Recommendations

• On crossing families of complete geometric graphs
• Crossing families
• Lines, line-point incidences and crossing families in dense sets

Cites work

• scientific article; zbMATH DE number 3951434 (Why is no real title available?)
• scientific article; zbMATH DE number 3339161 (Why is no real title available?)
• A lower bound on the number of triangulations of planar point sets
• Abstract order type extension and new results on the rectilinear crossing number
• An improved lower bound on the minimum number of triangulations
• Conway's conjecture for monotone thrackles
• Crossing families
• Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\)
• DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs
• Lines, line-point incidences and crossing families in dense sets
• Packing plane spanning trees and paths in complete geometric graphs
• Packing plane spanning trees into a point set
• Sweeps, arrangements and signotopes
• Two disjoint 5-holes in point sets

Cited in

(8)

• Line Transversals in Families of Connected Sets in the Plane
• The size of 3-cross-free families
• Perfect matchings with crossings
• At least \(n - 1\) intersection points in a connected family of \(n\) unit circles in the plane
• Crossing and intersecting families of geometric graphs on point sets
• Crossing families
• Lines, line-point incidences and crossing families in dense sets
• On the size of K-cross-free families

Describes a project that uses

Uses Software

• CaDiCaL
• DRAT-trim

This page was built for publication: On crossing-families in planar point sets

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