On crossing-families in planar point sets

被引：2

作者：

Aichholzer, Oswin ^{[1
]}

Kyncl, Jan ^{[2
]}

Scheucher, Manfred ^{[3
]}

Vogtenhuber, Birgit ^{[1
]}

Valtr, Pavel ^{[2
]}

机构：

[1] Graz Univ Technol, Inst Software Technol, Graz, Austria

[2] Charles Univ Prague, Fac Math & Phys, Dept Appl Math, Prague, Czech Republic

[3] Tech Univ Berlin, Inst Math, Berlin, Germany

来源：

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS | 2022年 / 107卷

基金：

欧盟地平线“2020”; 奥地利科学基金会;

关键词：

Crossing family; Point set; Order type; Geometric thrackle;

D O I：

10.1016/j.comgeo.2022.101899

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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 8 inverted right perpendicular pi/4inverted left perpendicular. Both results improve the previously best known bounds. (C) 2022 Elsevier B.V. All rights reserved.

引用

页数：8

共 20 条

[1] A lower bound on the number of triangulations of planar point sets
Aichholzer, O
Hurtado, F
Noy, M
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2004, 29 (02): : 135 - 145
[2] Aichholzer O., 2016, LIPICS, V51, P7
[3] Abstract order type extension and new results on the rectilinear crossing number
Aichholzer, Oswin
Krasser, Hannes
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2007, 36 (01): : 2 - 15
[4] Packing plane spanning trees and paths in complete geometric graphs
Aichholzer, Oswin
Hackl, Thomas
Korman, Matias
van Kreveld, Marc
Loffler, Maarten
Pilz, Alexander
Speckmann, Bettina
Welzl, Emo
[J]. INFORMATION PROCESSING LETTERS, 2017, 124 : 35 - 41
[5] CROSSING FAMILIES
ARONOV, B
ERDOS, P
GODDARD, W
KLEITMAN, DJ
KLUGERMAN, M
PACH, J
SCHULMAN, LJ
[J]. COMBINATORICA, 1994, 14 (02) : 127 - 134
[6] Balko M, 2015, DISCRETE COMPUT GEOM, V53, P107, DOI 10.1007/s00454-014-9644-z
[7] Biere A., 2019, DEP COMPUTER SCI S B, P8
[8] Packing plane spanning trees into apoint set
Biniaz, Ahmad
Garcia, Alfredo
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2020, 90
[9] Challenge, 2022, CGWEEK 2022 4 GEOMET
[10] Evans W., 2019, ARXIV190600191V1

← 1 2 →