On stabbing triangles by lines in 3-space
Aronov, Boris ; Matoušek, Jiří
Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995), p. 109-113 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 1995-01-01
Classification:  52B55,  52C99,  68U05 
@article{118736,
     author = {Boris Aronov and Ji\v r\'\i\ Matou\v sek},
     title = {On stabbing triangles by lines in 3-space},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {36},
     year = {1995},
     pages = {109-113},
     zbl = {0831.52011},
     mrnumber = {1334418},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118736}
}

Aronov, Boris; Matoušek, Jiří. On stabbing triangles by lines in 3-space. Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995) pp. 109-113. http://gdmltest.u-ga.fr/item/118736/

Agarwal P.K. Partitioning arrangements of lines: II. Applications, Discrete Comput. Geom. 5 (1990), 533-573. (1990) | MR 1067786 | Zbl 0709.68108

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.

Chazelle B.; Palios L. Triangulating a non-convex polytope, Discrete Comput. Geom. 5 (1990), 505-526. (1990) | MR 1064577

Chazelle B.; Welzl E. Quasi-optimal range searching in spaces of finite VC-dimension, Discrete Comput. Geom. 4 (1989), 467-489. (1989) | MR 1014739 | Zbl 0681.68081

Matoušek J.; Welzl E.; Wernisch L. Discrepancy and $\varepsilon$-approximations for bounded VC-dimension, Combinatorica 13 (1993), 455-466. (1993) | MR 1262921

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

Matoušek J. Efficient partition trees, Discrete Comput. Geom. 8 (1992), 315-334. (1992) | MR 1174360

Welzl E. private communication, 1992, .