On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of Kn
On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of Kn
复制标题
关于 Kn 几何图的 ≤k 边、交叉和等分线
DOI：
--
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
G. Salazar
中科院分区：
文献类型：
--
作者：
B. Ábrego;M. Cetina;S. Fernández;J. Leaños;G. Salazar
设 P 是平面上一般位置的点的集合。用直线段连接 P 中的所有点对。在这样的图中，线段交叉的数量用 $operatorname {cr}(P)$ 表示，是 P 的直线交叉数量。 P 的二等分线是穿过 P 的两个点的线，它将 P 的其余点（几乎）分成两半。 P 的减半线数用 h(P) 表示。类似地，k 边，0≤k≤n/2−1，是一条穿过 P 的两个点并在一侧恰好留下 P 的 k 个点的线。 P 的 ≤k 条边的数量用 E≤k(P) 表示。令 $overline {mathrm {cr}}(n)$、h(n) 和 E≤k(n) 分别表示平面上一般位置的所有 n 点集合 P 上的 $operatorname {cr}(P)$ 的最小值、h(P) 的最大值和 E≤k(P) 的最小值。我们证明，先前已知的 E≤k(n) 下界对于 k<⌈(4n−2)/9⌉ 是紧的，并且对于所有 k≥⌈(4n−2)/9⌉ 则改进它。这反过来又将 $overline {mathrm {cr}}(n)$ 的下限从 $0.37968 inom{n}{4}+varTheta (n^{3})$ 提高到 $frac{277}{729} inom{n}{4}+varTheta (n^{3})geq 0.37997 inom{n}{4}+varTheta (n^{3})$。我们还给出了所有 n≤27 的 $overline {mathrm {cr}}(n)$ 和 h(n) 的精确值。仅当 n≤18 和奇数 n≤21 的交叉数以及 n≤14 和奇数 n≤21 的减半线时，才知道精确值。
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 $operatorname {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 $overline {mathrm {cr}}(n)$, h(n), and E≤k(n) denote the minimum of $operatorname {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 $overline {mathrm {cr}}(n)$ from $0.37968inom{n}{4}+varTheta (n^{3})$ to $frac{277}{729}inom{n}{4}+varTheta (n^{3})geq 0.37997inom{n}{4}+varTheta (n^{3})$. We also give the exact values of $overline {mathrm {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.