On ≤k-Edges, Crossings, and Halving Lines of Geometric Drawings of K n
Tóm tắt
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.37968\binom{n}{4}+\varTheta (n^{3})$
to
$\frac{277}{729}\binom{n}{4}+\varTheta (n^{3})\geq 0.37997\binom{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.
Tài liệu tham khảo
Ábrego, B.M., Balogh, J., Fernández-Merchant, S., Leaños, J., Salazar, G.: An extended lower bound on the number of ≤k-edges to generalized configurations of points and the pseudolinear crossing number of K n . J. Comb. Theory, Ser. A 115, 1257–1264 (2008)
Ábrego, B.M., Cetina, M., Fernández-Merchant, S., Leaños, J., Salazar, G.: 3-symmetric and 3-decomposable drawings of K n . Discrete Appl. Math. 158, 1240–1258 (2010)
Ábrego, B.M., Fernández-Merchant, S., Leaños, J., Salazar, G.: The maximum number of halving lines and the rectilinear crossing number K n for n≤27. Electron. Notes Discrete Math. 30, 261–266 (2008)
Ábrego, B.M., Fernández-Merchant, S., Leaños, J., Salazar, G.: A central approach to bound the number of crossings in a generalized configuration. Electron. Notes Discrete Math. 30, 273–278 (2008)
Ábrego, B.M., Fernández-Merchant, S., Leaños, J., Salazar, G.: Recent developments on the number of (≤k)-sets, halving lines, and the rectilinear crossing number of K n . In: Proceedings of XII Encuentros de Geometría Computacional, Universidad de Valladolid, Spain, June 25–27, pp. 7–13 (2007). ISBN 978-84-690-6900-4
Ábrego, B.M., Fernández-Merchant, S.: Geometric drawings of K n with few crossings. J. Comb. Theory, Ser. A 114, 373–379 (2007)
Ábrego, B.M., Fernández-Merchant, S.: A lower bound for the rectilinear crossing number. Graphs Comb. 21, 293–300 (2005)
Andrzejac, A., Aronov, B., Har-Peled, S., Seidel, R., Welzl, E.: Results on k-sets and j-facets via continuous motions. In: Proceedings of the 14th Annual ACM Symposium on Computational Geometry, pp. 192–199 (1998)
Aichholzer, O.: On the rectilinear crossing number. Available online at http://www.ist.tugraz.at/staff/aichholzer/crossings.html
Aichholzer, O., García, J., Orden, D., Ramos, P.A.: New results on lower bounds for the number of (≤k)-facets. Electron. Notes Discrete Math. 29, 189–193 (2007)
Aichholzer, O., García, J., Orden, D., Ramos, P.: New lower bounds for the number of (≤k)-edges and the rectilinear crossing number of K n . Discrete Comput. Geom. 38, 1–14 (2007)
Balogh, J., Salazar, G.: k-sets, convex quadrilaterals, and the rectilinear crossing number of K n . Discrete Comput. Geom. 35, 671–690 (2006)
Beygelzimer, A., Radziszowski, S.: On halving line arrangements. Discrete Math. 257, 267–283 (2002)
Brass, P., Moser, W., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)
Cetina, M., Hernández-Vélez, C., Leaños, J., Villalobos, C.: Point sets that minimize (≤k)-edges, 3-decomposable drawings, and the rectilinear crossing number of K 30. Discrete Math. 311, 1646–1657 (2011)
Dey, T.K.: Improved bounds for planar k-sets and related problems. Discrete Comput. Geom. 19, 373–382 (1998)
Erdős, P., Lovász, L., Simmons, A., Straus, E.G.: Dissection graphs of planar point sets. In: Srivastava, J.N., et al. (eds.) A Survey of Combinatorial Theory, pp. 139–149. North-Holland, Amsterdam (1973)
Erdős, P., Guy, R.K.: Crossing number problems. Am. Math. Mon. 80, 52–58 (1973)
Goodman, J.E., Pollack, R.: On the combinatorial classification of nondegenerate configurations in the plane. J. Comb. Theory, Ser. A 29, 220–235 (1980)
Guy, R.K.: Latest results on crossing numbers. In: Recent Trends in Graph Theory, pp. 143–156. Springer, New York (1971)
Lovász, L.: On the number of halving lines. Ann. Univ. Sci. Bp. Rolando Eötvös Nomin., Sect. Math. 14, 107–108 (1971)
Lovász, L., Vesztergombi, K., Wagner, U., Welzl, E.: Convex quadrilaterals and k-sets. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs. Contemporary Mathematics Series, vol. 342, pp. 139–148. Am. Math. Soc., Providence (2004)
Nivasch, G.: An improved, simple construction of many halving edges. In: Goodman, J.E., et al. (eds.) Surveys on Discrete and Computational Geometry. Contemporary Mathematics Series, vol. 453, pp. 299–305. Am. Math. Soc., Providence (2008)
Pach, J., Radoičić, R., Tardos, G., Tóth, G.: Improving the Crossing Lemma by finding more crossings in sparse graphs. Discrete Comput. Geom. 36, 527–552 (2006)
Tamaki, H., Tokuyama, T.: A characterization of planar graphs by pseudo-line arrangements. Algorithmica 35, 269–285 (2003)
Tóth, G.: Point sets with many k-sets. Discrete Comput. Geom. 26, 187–194 (2001)
Welzl, E.: More on k-sets of finite sets in the plane. Discrete Comput. Geom. 1, 95–100 (1986)