On crossing-families in planar point sets

DOI10.1016/J.COMGEO.2022.101899zbMATH Open1491.05058arXiv2109.10705OpenAlexW3199619847WikidataQ114195497 ScholiaQ114195497MaRDI QIDQ2144455FDOQ2144455

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)

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (7)

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

Uses Software

• DRAT-trim
• CaDiCaL

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)