Spanning trees with low crossing number
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1991)
- Volume: 25, Issue: 2, page 103-123
- ISSN: 0988-3754
Access Full Article
top
How to cite
topMatoušek, Jiří. "Spanning trees with low crossing number." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 25.2 (1991): 103-123. <http://eudml.org/doc/92384>.
@article{Matoušek1991,
author = {Matoušek, Jiří},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {spanning tree; crossing number; deterministic algorithm; randomized (Las Vegas) algorithm; Monte Carlo algorithm; randomized algorithms},
language = {eng},
number = {2},
pages = {103-123},
publisher = {EDP-Sciences},
title = {Spanning trees with low crossing number},
url = {http://eudml.org/doc/92384},
volume = {25},
year = {1991},
}
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
PB - EDP-Sciences
VL - 25
IS - 2
SP - 103
EP - 123
LA - eng
KW - spanning tree; crossing number; deterministic algorithm; randomized (Las Vegas) algorithm; Monte Carlo algorithm; randomized algorithms
UR - http://eudml.org/doc/92384
ER -
References
top- 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. MR1064575
- 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. MR1163345
- 3. K. CLARKSON, New applications of random sampling in computational geometry, Discr. & Comput. Geometry, 1987, 2, pp. 195-222. Zbl0615.68037MR884226
- 4. B. CHAZELLE, Lower bounds on the complexity of polytope range searching, J. Amer. Math. Soc., 1989, 2, No. 4, pp. 637-666. Zbl0695.68032MR1001852
- 5. B. CHAZELLE and E. WELZL, Quasi-optimal range searching in spaces of finite VC-dimension, Discr. & Comput. Geometry, 1989, 4, pp. 467-490. Zbl0681.68081MR1014739
- 6. H. EDELSBRUNNER, Algorithms in combinatorial geometry, Springer-Verlag, 1987. Zbl0634.52001MR904271
- 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. Zbl0634.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. Zbl0688.68031MR1014738
- 9. H. EDELSBRUNNER, J. O'ROURKE and R. SEIDEL, Constructing arrangements of hyperplanes with applications, SIAM J. on Computing, 1984, 15, pp. 341-363. Zbl0603.68104
- 10. D. HAUSSLER and E. WELZL, ε-nets and simplex range queries, Discr. & Comput. Geometry, 1987, 2, pp. 127-151. Zbl0619.68056MR884223
- 11. D. G. KIRKPATRICK, Optimal search in planar subdivisions, S.I.A.M. J. on Computing, 1983, 12, pp. 28-35. Zbl0501.68034MR687800
- 12. F. P. PREPARATA and I. M. SHAMOS, Computational geometry - An introduction, Springer-Verlag, 1985. Zbl0759.68037MR805539
- 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. Zbl0247.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. MR1213461
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.