On ≤ k-Edges, Crossings, and Halving Lines of Geometric Drawings of K n
Article
-
- Overview
-
- Research
-
- Identity
-
- Additional Document Info
-
- View All
-
Overview
abstract
-
Let P be a set of points in general position in the plane. Join all pairs of points in P with straight line segments. The number of segment-crossings in such a drawing, denoted by cr(P), is the rectilinear crossing number of P. A halving line of P is a line passing through two points of P that divides the rest of the points of P in (almost) half. The number of halving lines of P is denoted by h(P). Similarly, a k-edge, 0 ≤ k≤n/2-1, is a line passing through two points of P and leaving exactly k points of P on one side. The number of ≤k-edges of P is denoted by E ≤k(P). Let ̄cr(n), h(n), and E ≤k(n) denote the minimum of cr(P), the maximum of h(P), and the minimum of E ≤k(P), respectively, over all sets P of n points in general position in the plane. We show that the previously best known lower bound on E ≤k(n) is tight for k< ⌈(4n-2)/9 ⌉ and improve it for all k ≥ ⌈(4n-2)/9 ⌉. This in turn improves the lower bound on ̄cr(n) from. We also give the exact values of ̄cr(n) and h(n) for all n ≤ 27. Exact values were known only for n ≤ 18 and odd n ≤ 21 for the crossing number, and for n≤14 and odd n≤21 for halving lines. © 2012 Springer Science%2bBusiness Media, LLC.
publication date
published in
Research
keywords
-
Allowable sequences; Geometric drawings; Halving lines; k-Edges; k-Sets; Rectilinear crossing numbers
Identity
Digital Object Identifier (DOI)
Additional Document Info
start page
end page
volume
issue