Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
combinatorial geometry; computational geometry; crossing number
combinatorial geometry; computational geometry; crossing number
Summary:
We give an example of a set $P$ of $3n$ points in $\Bbb R 3$ such that, for any partition of $P$ into triples, there exists a line stabbing $\Omega(\sqrt n)$ of the triangles determined by the triples.
References:
[Aga90] Agarwal P.K.: Partitioning arrangements of lines: II. Applications. Discrete Comput. Geom. 5 (1990), 533-573. MR 1067786 | Zbl 0709.68108
[CEGS89] Chazelle B., Edelsbrunner H., Guibas L.J., Sharir M.: Lines in space: combinatorics, algorithms, and applications. In: Proc. 21st Annual ACM Sympos. Theory Comput., 1989, pp. 382-393.
[CP90] Chazelle B., Palios L.: Triangulating a non-convex polytope. Discrete Comput. Geom. 5 (1990), 505-526. MR 1064577
[CW89] Chazelle B., Welzl E.: Quasi-optimal range searching in spaces of finite VC-dimension. Discrete Comput. Geom. 4 (1989), 467-489. MR 1014739 | Zbl 0681.68081
[MWW93] Matoušek J., Welzl E., Wernisch L.: Discrepancy and $\varepsilon$-approximations for bounded VC-dimension. Combinatorica 13 (1993), 455-466. MR 1262921
[Pac91] Pach J.: Geometric graphs. In J.E. Goodman, R. Pollack, and W. Steiger, editors, Computational Geometry: Papers from the DIMACS special year; Amer. Math. Soc., 1991. Zbl 1052.05004
[Mat92] Matoušek J.: Efficient partition trees. Discrete Comput. Geom. 8 (1992), 315-334. MR 1174360
[Wel92] Welzl E.: private communication, 1992.
Search
Partner of
