Spanning trees with low crossing number
Matoušek, Jiří
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 103-123 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1991-01-01
@article{ITA_1991__25_2_103_0,
     author = {Matou\v sek, Ji\v r\'\i },
     title = {Spanning trees with low crossing number},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {25},
     year = {1991},
     pages = {103-123},
     mrnumber = {1110979},
     zbl = {0732.68100},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 103-123. http://gdmltest.u-ga.fr/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 1064575

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 1163345

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

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

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 1014739 | Zbl 0681.68081

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

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 0634.68064

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 1014738 | Zbl 0688.68031

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 0603.68104

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

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

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

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 0247.60005

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 1213461