@article{4070,
  abstract     = {Let S be a set of n closed intervals on the x-axis. A ranking assigns to each interval, s, a distinct rank, p(s)∊ [1, 2,…,n]. We say that s can see t if p(s)<p(t) and there is a point p∊s∩t so that p∉u for all u with p(s)<p(u)<p(t). It is shown that a ranking can be found in time O(n log n) such that each interval sees at most three other intervals. It is also shown that a ranking that minimizes the average number of endpoints visible from an interval can be computed in time O(n 5/2). The results have applications to intersection problems for intervals, as well as to channel routing problems which arise in layouts of VLSI circuits.},
  author       = {Edelsbrunner, Herbert and Overmars, Mark and Welzl, Emo and Hartman, Irith and Feldman, Jack},
  issn         = {1029-0265},
  journal      = {International Journal of Computer Mathematics},
  number       = {3-4},
  pages        = {129 -- 144},
  publisher    = {Taylor & Francis},
  title        = {{Ranking intervals under visibility constraints}},
  doi          = {10.1080/00207169008803871},
  volume       = {34},
  year         = {1990},
}

@inproceedings{4071,
  abstract     = {We show that a triangulation of a set of n points in the plane that minimizes the maximum angle can be computed in time O(n2 log n) and space O(n). In the same amount of time and space we can also handle the constrained case where edges are prescribed. The algorithm iteratively improves an arbitrary initial triangulation and is fairly easy to implement.},
  author       = {Edelsbrunner, Herbert and Tan, Tiow and Waupotitsch, Roman},
  booktitle    = {Proceedings of the 6th annual symposium on Computational geometry},
  isbn         = {978-0-89791-362-1},
  location     = {Berkley, CA, United States},
  pages        = {44 -- 52},
  publisher    = {ACM},
  title        = {{An O(n^2log n) time algorithm for the MinMax angle triangulation}},
  doi          = {10.1145/98524.98535},
  year         = {1990},
}

@article{4072,
  abstract     = {We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3– n 2/3+2 +n) for any&gt;0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any&gt;0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n) log2 n logm).},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {161 -- 196},
  publisher    = {Springer},
  title        = {{The complexity and construction of many faces in arrangements of lines and of segments}},
  doi          = {10.1007/BF02187784},
  volume       = {5},
  year         = {1990},
}

@inproceedings{4073,
  abstract     = {A number of rendering algorithms in computer graphics sort three-dimensional objects by depth and assume that there is no cycle that makes the sorting impossible. One way to resolve the problem caused by cycles is to cut the objects into smaller pieces. The problem of estimating how many such cuts are always sufficient is addressed. A few related algorithmic and combinatorial geometry problems are considered.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Pollack, Richard and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack},
  booktitle    = {31st Annual Symposium on Foundations of Computer Science},
  isbn         = {0-8186-2082-X},
  location     = {St. Louis, MO, United States of America},
  pages        = {242 -- 251},
  publisher    = {IEEE},
  title        = {{Counting and cutting cycles of lines and rods in space}},
  doi          = {10.1109/FSCS.1990.89543},
  year         = {1990},
}

@article{4074,
  abstract     = {We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.},
  author       = {Clarkson, Kenneth and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Welzl, Emo},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {99 -- 160},
  publisher    = {Springer},
  title        = {{Combinatorial complexity bounds for arrangements of curves and spheres}},
  doi          = {10.1007/BF02187783},
  volume       = {5},
  year         = {1990},
}

@article{4075,
  abstract     = {A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determining pairs of vertices that see each other in a star-shaped polygon. A linear-time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r&gt; 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.},
  author       = {Dobkin, David and Edelsbrunner, Herbert and Overmars, Mark},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  number       = {4},
  pages        = {561 -- 571},
  publisher    = {Springer},
  title        = {{Searching for empty convex polygons}},
  doi          = {10.1007/BF01840404},
  volume       = {5},
  year         = {1990},
}

@inproceedings{4076,
  abstract     = {We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in Ed in time O(Td(N, N) logd N), where Td(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in Ed. If Td(N, N) = Ω(N1+ε), for some fixed ε &gt; 0, then the running time improves to O(Td(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closets pair in expected time O((nm log n log m)2/3+m log2 n + n log2 m) in E3, which yields an O(N4/3log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in E3.},
  author       = {Agarwal, Pankaj and Edelsbrunner, Herbert and Schwarzkopf, Otfried and Welzl, Emo},
  booktitle    = {Proceedings of the 6th annual symposium on Computational geometry},
  isbn         = {978-0-89791-362-1},
  location     = {Berkeley, CA, United States},
  pages        = {203 -- 210},
  publisher    = {ACM},
  title        = {{ Euclidean minimum spanning trees and bichromatic closest pairs}},
  doi          = {10.1145/98524.98567},
  year         = {1990},
}

@inproceedings{4077,
  abstract     = {We prove that for any set S of n points in the plane and n3-α triangles spanned by the points of S there exists a point (not necessarily of S) contained in at least n3-3α/(512 log25 n) of the triangles. This implies that any set of n points in three - dimensional space defines at most 6.4n8/3 log5/3 n halving planes.},
  author       = {Aronov, Boris and Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Wenger, Rephael},
  booktitle    = {Proceedings of the 6th annual symposium on Computational geometry},
  isbn         = {978-0-89791-362-1},
  location     = {Berkley, CA, United States},
  pages        = {112 -- 115},
  publisher    = {ACM},
  title        = {{Points and triangles in the plane and halving planes in space}},
  doi          = {10.1145/98524.98548},
  year         = {1990},
}

@inproceedings{4078,
  abstract     = {In this paper we derived combinatorial point selection results for geometric objects defined by pairs of points. In a nutshell, the results say that if many pairs of a set of n points in some fixed dimension each define a geometric object of some type, then there is a point covered by many of these objects. Based on such a result for three-dimensional spheres we show that the combinatorial size of the Delaunay triangulation of a point set in space can be reduced by adding new points. We believe that from a practical point of view this is the most important result of this paper.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Seidel, Raimund and Sharir, Micha},
  booktitle    = {Proceedings of the 6th annual symposium on computational geometry},
  isbn         = {978-0-89791-362-1},
  location     = {Berkley, CA, United States},
  pages        = {116 -- 127},
  publisher    = {ACM},
  title        = {{Slimming down by adding; selecting heavily covered points}},
  doi          = {10.1145/98524.98551},
  year         = {1990},
}

@article{4310,
  author       = {Barton, Nicholas H and Jones, Steve},
  issn         = {1476-4687},
  journal      = {Nature},
  pages        = {415 -- 416},
  publisher    = {Nature Publishing Group},
  title        = {{The language of the genes}},
  doi          = {10.1038/346415a0},
  volume       = {346},
  year         = {1990},
}

@inbook{4311,
  author       = {Barton, Nicholas H and Clark, A.},
  booktitle    = {Population biology: Ecological and evolutionary viewpoints},
  editor       = {Wöhrmann, Klaus and Jain, Subodh},
  isbn         = { 978-3642744761},
  pages        = {115 -- 174},
  publisher    = {Springer},
  title        = {{Population structure and processes in evolution}},
  doi          = {10.1007/978-3-642-74474-7_5},
  year         = {1990},
}