2011/02/24 by Bernardo M. Ábrego, M. Cetina, Ábrego, Bernardo M. +7 · 2 citations
Computer Science · Engineering · #05C62 #52C10 #52C30 #52C45 #60D05 #68R10 #Advanced Numerical Analysis Techniques #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #and 52A22
paper · pdf · doi:10.48550/arxiv.1102.5065
openalex publication_date 2011/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \crg(P), is the rectilinear crossing number of P. A halving line of P is a line passing though 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 \rcr(n), h(n), and E≤ k(n) denote the minimum of \crg(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