@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 Herbert Edelsbrunner and Guibas, Leonidas J and Pollack, Richard and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack},
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,
author = {Clarkson, Kenneth L and Herbert Edelsbrunner and Guibas, Leonidas J and Sharir, Micha and Welzl, Emo},
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> 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.},
author = {Dobkin, David P and Herbert Edelsbrunner and Overmars, Mark H},
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 ε > 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 K and Herbert Edelsbrunner and Schwarzkopf, Otfried and Welzl, Emo},
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 Herbert Edelsbrunner and Guibas, Leonidas J and Sharir, Micha and Wenger, Rephael},
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 Herbert Edelsbrunner and Guibas, Leonidas J and Hershberger, John E and Seidel, Raimund and Sharir, Micha},
pages = {116 -- 127},
publisher = {ACM},
title = {{Slimming down by adding; selecting heavily covered points}},
doi = {10.1145/98524.98551},
year = {1990},
}
@misc{4310,
author = {Nicholas Barton and Jones, Steve},
booktitle = {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 = {Nicholas Barton and Clark,A.},
booktitle = {Population biology: ecological and evolutionary viewpoints},
editor = {Wöhrmann, Klaus and Jain, Subodh K},
pages = {115 -- 174},
publisher = {Springer},
title = {{Population structure}},
year = {1990},
}
@inproceedings{4510,
abstract = {The interleaving model is both adequate and sufficiently abstract to allow for the practical specification and verification of many properties of concurrent systems. We incorporate real time into this model by defining the abstract notion of a real-time transition system as a conservative extension of traditional transition systems: qualitative fairness requirements are replaced (and superseded) by quantitative lower-bound and upper-bound real-time requirements for transitions.
We present proof rules to establish lower and upper real-time bounds for response properties of real-time transition systems. This proof system can be used to verify bounded-invariance and bounded-response properties, such as timely termination of shared-variables multi-process systems, whose semantics is defined in terms of real-time transition systems.},
author = {Thomas Henzinger and Manna, Zohar and Pnueli,Amir},
pages = {717 -- 730},
publisher = {IEEE},
title = {{An interleaving model for real time}},
year = {1990},
}
@inproceedings{4522,
author = {Thomas Henzinger},
pages = {281 -- 296},
publisher = {ACM},
title = {{Half-order modal logic: How to prove real-time properties}},
doi = {10.1145/93385.93429},
year = {1990},
}