On ≤ k-Edges, Crossings, and Halving Lines of Geometric Drawings of K n Article uri icon

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

  • 2012-01-01