| Title:
|
On stabbing triangles by lines in 3-space (English) |
| Author:
|
Aronov, Boris |
| Author:
|
Matoušek, Jiří |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
36 |
| Issue:
|
1 |
| Year:
|
1995 |
| Pages:
|
109-113 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
combinatorial geometry |
| Keyword:
|
computational geometry |
| Keyword:
|
crossing number |
| MSC:
|
52B55 |
| MSC:
|
52C99 |
| MSC:
|
68U05 |
| idZBL:
|
Zbl 0831.52011 |
| idMR:
|
MR1334418 |
| . |
| Date available:
|
2009-01-08T18:16:18Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118736 |
| . |
| Reference:
|
[Aga90] Agarwal P.K.: Partitioning arrangements of lines: II. Applications.Discrete Comput. Geom. 5 (1990), 533-573. Zbl 0709.68108, MR 1067786 |
| Reference:
|
[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. |
| Reference:
|
[CP90] Chazelle B., Palios L.: Triangulating a non-convex polytope.Discrete Comput. Geom. 5 (1990), 505-526. MR 1064577 |
| Reference:
|
[CW89] Chazelle B., Welzl E.: Quasi-optimal range searching in spaces of finite VC-dimension.Discrete Comput. Geom. 4 (1989), 467-489. Zbl 0681.68081, MR 1014739 |
| Reference:
|
[MWW93] Matoušek J., Welzl E., Wernisch L.: Discrepancy and $\varepsilon$-approximations for bounded VC-dimension.Combinatorica 13 (1993), 455-466. MR 1262921 |
| Reference:
|
[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 |
| Reference:
|
[Mat92] Matoušek J.: Efficient partition trees.Discrete Comput. Geom. 8 (1992), 315-334. MR 1174360 |
| Reference:
|
[Wel92] Welzl E.: private communication, 1992.. |
| . |
