Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn

József Balogh; Gelasio Salazar

Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of K_n

Research output: Contribution to journal › Conference article › peer-review

Abstract

We use circular sequences to give an improved lower bound on the minimum number of (≤ k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number □ (S) of convex quadrilaterals determined by the points in S is at least 0.37553(₄ⁿ) + O(n³). This in turn implies that the rectilinear crossing number ̄cr(K_n) of the complete graph K_n is at least 0.37553(₄ⁿ) + O(n³). These improved bounds refine results recently obtained by Abrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.

Original language	English (US)
Pages (from-to)	25-35
Number of pages	11
Journal	Lecture Notes in Computer Science
Volume	3383
State	Published - 2004
Externally published	Yes
Event	12th International Symposium on Graph Drawing, GD 2004 - New York, NY, United States Duration: Sep 29 2004 → Oct 2 2004

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Library availability

Discover UIUC Full Text

Cite this

@article{9554c1025da54c04a81f869768755fc8,

title = "Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn",

abstract = "We use circular sequences to give an improved lower bound on the minimum number of (≤ k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number □ (S) of convex quadrilaterals determined by the points in S is at least 0.37553(4n) + O(n3). This in turn implies that the rectilinear crossing number{\= }cr(Kn) of the complete graph Kn is at least 0.37553(4n) + O(n3). These improved bounds refine results recently obtained by Abrego and Fern{\'a}ndez-Merchant, and by Lov{\'a}sz, Vesztergombi, Wagner and Welzl.",

author = "J{\'o}zsef Balogh and Gelasio Salazar",

year = "2004",

language = "English (US)",

volume = "3383",

pages = "25--35",

journal = "Lecture Notes in Computer Science",

issn = "0302-9743",

publisher = "Springer",

note = "12th International Symposium on Graph Drawing, GD 2004 ; Conference date: 29-09-2004 Through 02-10-2004",

}

TY - JOUR

T1 - Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of Kn

AU - Balogh, József

AU - Salazar, Gelasio

PY - 2004

Y1 - 2004

N2 - We use circular sequences to give an improved lower bound on the minimum number of (≤ k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number □ (S) of convex quadrilaterals determined by the points in S is at least 0.37553(4n) + O(n3). This in turn implies that the rectilinear crossing number ̄cr(Kn) of the complete graph Kn is at least 0.37553(4n) + O(n3). These improved bounds refine results recently obtained by Abrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.

AB - We use circular sequences to give an improved lower bound on the minimum number of (≤ k)-sets in a set of points in general position. We then use this to show that if S is a set of n points in general position, then the number □ (S) of convex quadrilaterals determined by the points in S is at least 0.37553(4n) + O(n3). This in turn implies that the rectilinear crossing number ̄cr(Kn) of the complete graph Kn is at least 0.37553(4n) + O(n3). These improved bounds refine results recently obtained by Abrego and Fernández-Merchant, and by Lovász, Vesztergombi, Wagner and Welzl.

UR - http://www.scopus.com/inward/record.url?scp=24144482643&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24144482643&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:24144482643

SN - 0302-9743

VL - 3383

SP - 25

EP - 35

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 12th International Symposium on Graph Drawing, GD 2004

Y2 - 29 September 2004 through 2 October 2004

ER -

Improved bounds for the number of (≤ k)-Sets, convex quadrilaterals, and the rectilinear crossing number of K_n

Abstract

ASJC Scopus subject areas

Library availability

Related links

Fingerprint

Cite this