@article{4116,
abstract = {A straight line that intersects all members of a set S of objects in the real plane is called a transversal of S. Geometric transforms are described that reduce transversal problems for various types of objects to convex hull problems for points. These reductions lead to efficient algorithms for finding transversals which are also described. Applications of the algorithms are found in computer graphics: “Reproduce the line displayed by a collection of pixels”, and in statistics: “Find the line that minimizes the maximum distance from a collection of (weighted) points in the plane”.},
author = {Herbert Edelsbrunner},
journal = {Theoretical Computer Science},
number = {1},
pages = {55 -- 69},
publisher = {Elsevier},
title = {{Finding Transversals for Sets of Simple Geometric-Figures}},
doi = {10.1016/0304-3975(85)90005-2},
volume = {35},
year = {1985},
}
@misc{4325,
author = {Jones, Steve and Nicholas Barton},
booktitle = {Nature},
pages = {668 -- 668},
publisher = {Nature Publishing Group},
title = {{Haldane's Rule OK}},
doi = {10.1038/314668a0},
volume = {314},
year = {1985},
}
@article{4112,
abstract = {The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlogd−1n + k) time using only O(n) space.},
author = {Herbert Edelsbrunner and Overmars, Mark H},
journal = {Journal of Algorithms},
number = {4},
pages = {515 -- 542},
publisher = {Academic Press},
title = {{Batched dynamic solutions to decomposable searching problems}},
doi = {10.1016/0196-6774(85)90030-6},
volume = {6},
year = {1985},
}
@article{4326,
author = {Nicholas Barton and Hewitt, Godfrey M},
journal = {Annual Review of Ecology and Systematics},
pages = {113 -- 148},
publisher = {Annual Reviews},
title = {{Analysis of hybrid zones}},
doi = {10.1146/annurev.es.16.110185.000553},
volume = {16},
year = {1985},
}
@article{4113,
abstract = {Let S denote a set of n points in the Euclidean plane. A subset S′ of S is termed a k-set of S if it contains k points and there exists a straight line which has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum number of k-sets which can be realized by a set of n points. This paper studies the asymptotic behaviour of fk(n) as this function has applications to a number of problems in computational geometry. A lower and an upper bound on fk(n) is established. Both are nontrivial and improve bounds known before. In particular, is shown by exhibiting special point-sets which realize that many k-sets. In addition, is proved by the study of a combinatorial problem which is of interest in its own right.},
author = {Herbert Edelsbrunner and Welzl, Emo},
journal = {Journal of Combinatorial Theory Series A},
number = {1},
pages = {15 -- 29},
publisher = {Elsevier},
title = {{On the number of line separations of a finite set in the plane}},
doi = {10.1016/0097-3165(85)90017-2},
volume = {38},
year = {1985},
}