Spanning trees with low crossing number
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 2, pp. 103-123.
@article{ITA_1991__25_2_103_0,
     author = {Matou\v{s}ek, Ji\v{r}{\'\i}},
     title = {Spanning trees with low crossing number},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {103--123},
     publisher = {EDP-Sciences},
     volume = {25},
     number = {2},
     year = {1991},
     mrnumber = {1110979},
     zbl = {0732.68100},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1991__25_2_103_0/}
}
TY  - JOUR
AU  - Matoušek, Jiří
TI  - Spanning trees with low crossing number
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1991
SP  - 103
EP  - 123
VL  - 25
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1991__25_2_103_0/
LA  - en
ID  - ITA_1991__25_2_103_0
ER  - 
%0 Journal Article
%A Matoušek, Jiří
%T Spanning trees with low crossing number
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1991
%P 103-123
%V 25
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1991__25_2_103_0/
%G en
%F ITA_1991__25_2_103_0
Matoušek, Jiří. Spanning trees with low crossing number. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 2, pp. 103-123. http://www.numdam.org/item/ITA_1991__25_2_103_0/

1. P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its applications, Proc. 5. Ann. ACM Symposium on Comput. Geometry (1989), pp. 11-21; full version to appear in Discrete & Comput. Geometry, 1990. | MR

2. P. K Agarwal, Ray shooting and other applications of spanning trees with low stabbing number, Proc. 5. Ann. ACM Symposium on Comput. Geometry (1989), pp. 315-325; full version to appear in Discrete & Comput. Geometry, 1990. | MR

3. K. Clarkson, New applications of random sampling in computational geometry, Discr. & Comput. Geometry, 1987, 2, pp. 195-222. | MR | Zbl

4. B. Chazelle, Lower bounds on the complexity of polytope range searching, J. Amer. Math. Soc., 1989, 2, No. 4, pp. 637-666. | MR | Zbl

5. B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension, Discr. & Comput. Geometry, 1989, 4, pp. 467-490. | MR | Zbl

6. H. Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag, 1987. | MR | Zbl

7. H. Edelsbrunner and E. Welzl, Halfplanar range search in linear space and O(n0-695) query time, Inf. Proc. Letters, 1986, 23, No. 6, pp. 289-293. | Zbl

8. H. Edelsbrunner, L. Guibas, J. Herschberger, R. Seidel, M. Sharir, J. Snoeyink and E. Welzl, Implicitly representing arrangements of lines or segments, Discr. & Comput. Geometry, 1989, 4, pp. 433-466. | MR | Zbl

9. H. Edelsbrunner, J. O'Rourke and R. Seidel, Constructing arrangements of hyperplanes with applications, SIAM J. on Computing, 1984, 15, pp. 341-363. | Zbl

10. D. Haussler and E. Welzl, ε-nets and simplex range queries, Discr. & Comput. Geometry, 1987, 2, pp. 127-151. | MR | Zbl

11. D. G. Kirkpatrick, Optimal search in planar subdivisions, S.I.A.M. J. on Computing, 1983, 12, pp. 28-35. | MR | Zbl

12. F. P. Preparata and I. M. Shamos, Computational geometry - An introduction, Springer-Verlag, 1985. | MR | Zbl

13. V. N. Vapnik and A. Ya. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory Probab. Appl., 1971, 16, pp. 264-280. | Zbl

14. E. Welzl, Partition trees for triangle counting and other range searching problems, 4. A.C.M. Symposium on Comput. Geometry, 1988, pp. 23-33. | MR