\begin{thebibliography}{99}

 

\bibitem{AS89}
{C. Aragon, R. Seidel: ``Randomized Search Trees", Proc. 30th IEEE Symposium 
 on Foundations of Computer Science, 540-545, 1989}

\bibitem{AHU83} 
{A.V. Aho, J.E. Hopcroft, J.D. Ullman: ``Data Structures and 
Algorithms'', Addison-Wesley Publishing Company, 1983}

\bibitem{AVL62} 
{G.M. Adelson-Veslkii, Y.M. Landis: ``An Algorithm for the Organization of
Information", Doklady Akademi Nauk, Vol. 146, 263-266, 1962}

\bibitem{B79}
{J.L. Bentley: ``Decomposable Searching Problems", Information Processing
Letters, Vol. 8, 244-252, 1979}

\bibitem{Bentley:Multi}
{J.L. Bentley: ``Multi-dimensional Divide and Conquer", CACM Vol 23, 214-229, 1980}

\bibitem{Be58}
{R.E. Bellman: ``On a Routing Problem", Quart. Appl. Math. 16, 87-90, 1958}

\bibitem{BO79}
{J.L. Bentley, Th. Ottmann: ``Algorithms for Reporting and Counting
Geometric Intersections", IEEE Trans. on Computers C 28, 643-647, 1979 }

\bibitem{BC72}
{R. Bayer, E. McCreight: ``Organizatino and Maintenance of Large Ordered 
 Indizes", Acta Informatica, Vol. 1, 173-189, 1972}

\bibitem{BM80} 
{N. Blum, K. Mehlhorn: ``On the Average Number of Rebalancing Operations in 
Weight-Balanced Trees", Theoretical Computer Science 11, 303-320, 1980}

\bibitem{BMS:ESA}
Ch. Burnikel, K.~Mehlhorn, and St. Schirra.
\newblock How to compute the {V}oronoi diagram of line segments: {T}heoretical
  and experimental results.
\newblock In {\em LNCS}, volume 855, pages 227--239. Springer-Verlag Berlin/New
  York, 1994.
\newblock Proceedings of ESA'94.

\bibitem{CLR90}
{T.H. Cormen, C.E. Leiserson, R.L. Rivest: ``Introduction to Algorithms'', 
MIT Press/McGraw-Hill Book Company, 1990 }

\bibitem{CT76}
{D. Cheriton, R.E. Tarjan: ``Finding Minimum Spanning Trees", SIAM Journal
 of Computing, Vol. 5, 724-742, 1976}

\bibitem{De92}
{ O. Devillers: ``Robust and Efficient Implementation of the Delaunay Tree",
Technical Report, INRIA, 1992}

\bibitem{Di59}
{E.W. Dijkstra: ``A Note on Two Problems in Connection With Graphs", Num.
 Math., Vol. 1, 269-271, 1959}

\bibitem{DKMMRT88} 
{M. Dietzfelbinger, A. Karlin, K.Mehlhorn, F. Meyer 
auf der Heide, H. Rohnert, R. Tarjan: ``Upper and Lower Bounds for
the Dictionary Problem'', Proc. of the 29th Annual IEEE Symposium on
Foundations of Computer Science, 1988}

\bibitem{DSST89}
{J.R. Driscoll, N.Sarnak, D. Sleator, R.E. Tarjan:
``Making Data Structures Persistent'', Proc. of the 18th Annual ACM 
Symposium on Theory of Computing, 109-121, 1986}

\bibitem{E65}
{J. Edmonds: ``Paths, Trees, and Flowers", Canad. J. Math., Vol. 17, 449-467,
1965}

\bibitem{Ed82}
{H. Edelsbrunner: ``Intersection Problems in Computational Geometry",
Ph.D. thesis, TU Graz, 1982}

\bibitem{EKZ77}
{P.v. Emde Boas, R. Kaas, E. Zijlstra: ``Design and Implementation of an 
 Efficient Priority Queue", Math. Systems Theory, Vol. 10, 99-127, 1977}

\bibitem{fgkss:cgalarticle}
A.~Fabri, G.-J. Giezeman, L.~Kettner, S.~Schirra, and S.~Sch{\"o}nherr.
\newblock The {C}{G}{A}{L} kernel: A basis for geometric computation.
\newblock {\em First ACM Workshop on Applied Computational Geometry}, 1996.


\bibitem{Fa48} 
{I. Fary: ``On Straight Line Representing of Planar Graphs", Acta. Sci. Math.
 Vol. 11, 229-233, 1948}

\bibitem{Fl62}
{F.W. Floyd: ``Algorithm 97: Shortest Paths", Communcication of the ACM,
 Vol. 5, p. 345, 1962}

\bibitem{Fortune-vWijk}
S.~Fortune and C.~{van Wyk}.
\newblock Efficient exact arithmetic for computational geometry.
\newblock {\em Proc. of the 9th Symp. on Computational Geometry}, pages
  163--171, 1993.

\bibitem{FT87} 
{M.L. Fredman, and R.E. Tarjan: ``Fibonacci Heaps and Their Uses in
 Improved Network Optimization Algorithms'', Journal of the ACM, Vol. 34, 
 596-615, 1987}

\bibitem{G74} 
{H.N.Gabow: 
``Implementation of algorithms for maximum matching on nonbipartite
 graphs", 
Ph.D. thesis, Stanford Univ., Stanford, CA, 1974}

\bibitem{GK79}
{A. Goralcikova, V. Konbek: ``A Reduct and Closure Algorithm for Graphs",
 Mathematical Foundations of Computer Science, LNCS 74, 301-307, 1979}

\bibitem{GOP90}
{K.E. Gorlen, S.M. Orlow, P.S. Plexico: ``Data Abstraction and Object-Oriented
Programming in \CC'', John Wiley \& Sons, 1990}

\bibitem{GS78}
{L.J. Guibas, R. Sedgewick: `` A Dichromatic Framework for Balanced Trees",
 Proceedings of the 19th IEEE Symposium on Foundations of Computer Science,
 8-21, 1978}

\bibitem{GT88}
{Goldberg, R.E.Tarjan: ``A New Approach to the Maximum Flow Problem",
 Journal of the ACM, Vol. 35, 921-940, 1988 }

\bibitem{HK75}
{J.E. Hopcroft, R.M. Karp: ``An $O(n^{2.5})$ Algorithm for Matching in 
 Bipartite Graphs", SIAM Journal of Computing, Vol. 4, 225-231, 1975}

\bibitem{HT74}
{J.E. Hopcroft, R.E. Tarjan: ``Efficient Planarity Testing", Journal of
 the ACM, Vol. 21, 549-568, 1974}

\bibitem{HU89}
{T. Hagerup, C. Uhrig: ``Triangulating a Planar Map Without Introducing
 multiple Arcs", unpublished, 1989 }

\bibitem{Ka62}
{A.B. Kahn: ``Topological Sorting of Large Networks", Communications of the
 ACM, Vol. 5, 558-562, 1962}

\bibitem{Knuth-Levy}
D.~Knuth and S.~Levy.
\newblock {\em The {CWEB} System of Structured Documentation, Version 3.0}.
\newblock Addison-Wesley, 1993.

\bibitem{Kr56}
{J.B. Kruskal: ``On the Shortest Spanning Subtree of a Graph and the Travelling
 Salesman Problem", Proc. American Math. Society 7, 48-50, 1956}

\bibitem{L76}
{E.L. Lawler: 
``Combinatorial Optimization: Networks and Matroids", 
Holt, Rinehart and Winston, New York, 1976}

\bibitem{Li89} 
{S.B. Lippman: ``\CC Primer'', Addison-Wesley, Publishing Company, 1989}

\bibitem{Lu78} 
{G.S. Luecker: ``A Data Structure for Orthogonal Range Queries", 
Proc. 19th IEEE Symposium on Foundations of Computer Science, 28-34, 1978}

\bibitem{M84} 
{K. Mehlhorn: ``Data Structures and Algorithms'', Vol. 1--3,
Springer Publishing Company, 1984}

\bibitem{MC80}
{D.M. McCreight: ``Efficient Algorithms for Enumerating Intersecting Intervals",
 Xerox Parc Report, CSL-80-09, 1980}

\bibitem{MC81}
{D.M. McCreight: ``Priority Search Trees", Xerox Parc Report, CSL-81-05, 1981}

\bibitem{Mignotte:Buch}
M.~Mignotte.
\newblock {\em Mathematics for Computer Algebra}.
\newblock Springer Verlag, 1992.

\bibitem{MN89} 
{K. Mehlhorn, S. N\"aher: `` LEDA, a Library of Efficient Data Types and
Algorithms'', TR A 04/89, FB10, Universit\"at des Saarlandes, 
Saarbr\"ucken, 1989}

\bibitem{MN95} 
{K. Mehlhorn, S. N\"aher: `` LEDA, a Platform for Combinatorial and Geometric 
Computing'', Communications of the ACM, Vol. 38, No. 1, 96-102, 1995 }

\bibitem{LEDAbook} 
K. Mehlhorn, S. N\"aher.
\newblock {LEDA}, a Platform for Combinatorial and Geometric Computing.
\newblock book, in preparation. For sample chapters see the LEDA www-pages.

\bibitem{Me-Naeher:sweep}
K.~Mehlhorn and S.~N\"aher.
\newblock Implementation of a sweep line algorithm for the straight line
  segment intersection problem.
\newblock Technical Report MPI-I-94-160, Max-Planck-Institut f\"ur Informatik,
  Saarbr\"ucken, 1994.

\bibitem{Me-Naeher:IFIP94}
K.~Mehlhorn and St. N\"aher.
\newblock The implementation of geometric algorithms.
\newblock In {\em 13th World Computer Congress IFIP94}, volume~1, pages
  223--231. Elsevier Science B.V. North-Holland, Amsterdam, 1994.

\bibitem{Mignotte:book}
M.~Mignotte
\newblock Mathematics for Computer Algebra.
\newblock Springer Verlag.
\newblock 1992

\bibitem{N90}
S. N\"aher:
``LEDA2.0  User Manual'',
technischer Bericht A 17/90, Fachbereich Informatik,
Universit\"at des Saarlandes, Saarbr\"ucken, 1990

\bibitem{over:cgalarticle}
M.~H. Overmars.
\newblock Designing the computational geometry algorithms library {C}{G}{A}{L}.
\newblock {\em In Proceedings First ACM Workshop on Applied Computational
  Geometry}, 1996.


\bibitem{Pu90}
{W. Pugh: ``Skip Lists: A Probabilistic Alternative to Balanced Trees",
 Communications of the ACM, Vol. 33, No. 6, 668-676, 1990} 

\bibitem{Ramsey:noweb}
N.~Ramsey.
\newblock Literate programming simplified.
\newblock {\em IEEE Software}, pages 97--105, 1994.


\bibitem{SW94}
{M. Stoer and F. Wagner: ``A Simple Min Cut Algorithm",
 Algorithms -- ESA '94, LNCS 855, 141- 147, 1994}

\bibitem{S91} 
{B. Stroustrup: ``The \CC Programming Language, Second Edition", 
Addison-Wesley Publishing Company, 1991}

\bibitem{SV87}
{J.T. Stasko, J.S. Vitter: ``Pairing Heaps: Experiments and Analysis",
 Communications of the ACM, Vol. 30, 234-249, 1987}

\bibitem{T72}
{R.E. Tarjan: ``Depth First Search an Linear Graph Algorithms", SIAM Journal
 of Computing, Vol. 1, 146-160, 1972}

\bibitem{T83} 
{R.E. Tarjan: ``Data Structures and Network Algorithms'',
CBMS-NSF Regional Conference Series in Applied Mathematics,
Vol. 44, 1983}

\bibitem{We92} 
{M. Wenzel: ``W\"orterb\"ucher f\"ur ein beschr\"anktes Universum",
Diplomarbeit, Fachbereich Informatik, Universit\"at des Saarlandes,
1992}

\bibitem{Whi73}
{A.G. White: ``Graphs,Groups, and Surfaces'',
North Holland, 1973}

\bibitem{Wi85}
{D.E. Willard: ``New Data Structures for Orthogonal Queries", SIAM Journal
of Computing, 232-253, 1985}

\end{thebibliography}
