Lines, line-point incidences and crossing families in dense sets
type: Item
instance of: scholarly article
title: Lines, line-point incidences and crossing families in dense sets
zbMATH Open document ID: 0871.52013
DOI: 10.1007/BF01844852
published in: Combinatorica
publication date: 1996-10-20T00:00:00Z
review text: A set \(P\) of \(n\) points in the plane is called \(\alpha\)-dense if the ratio between the maximum and the minimum distance in \(P\) is at most \(\alpha\sqrt n\). By a crossing family we mean a set of line segments such that the relative interiors of every two of them intersect. The author proves that if a set \(P\) on \(n\) points is \(\alpha\)-dense, where \(\alpha\geq\sqrt {2\sqrt 3}/ \pi\), then there exists a crossing family with end-points in \(P\) whose size is \(\Omega(n (\log n)^{-4\log \log\log n+c})\), where \(c=4\log (1000\alpha^2+8)\) and where the base of logarithms is 2.
reviewed by: Marek Lassak
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 936877
zbMATH Keywords: distance
zbMATH Keywords: crossing family
zbMATH Keywords: line segments
author: Pavel Valtr
MaRDI profile type: Publication
cites work: Geometric methods in the study of irregularities of distribution
cites work: Crossing families
cites work: The maximum size of a convex polygon in a restricted set of points in the plane
cites work: On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
cites work: Q4011323
cites work: Extremal problems in discrete geometry
cites work: Convex independent sets and 7-holes in restricted planar point sets
cites work: Q4861416
full work available at URL: https://doi.org/10.1007/bf01844852
OpenAlex ID: W2065078485
description: scientific article; zbMATH DE number 936877