@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{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{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{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},
}
@article{4120,
abstract = {Let P be a set of n points in the Euclidean plane and let C be a convex figure. We study the problem of preprocessing P so that for any query point q, the points of P in C+q can be retrieved efficiently. If constant time sumces for deciding the inclusion of a point in C, we then demonstrate the existence of an optimal solution: the algorithm requires O(n) space and O(k + log n) time for a query with output size k. If C is a disk, the problem becomes the wellknown fixed-radius neighbour problem, to which we thus provide the first known optimal solution.},
author = {Chazelle, Bernard and Herbert Edelsbrunner},
journal = {Journal of Symbolic Computation},
number = {1},
pages = {47 -- 56},
publisher = {Elsevier},
title = {{Optimal solutions for a class of point retrieval problems}},
doi = {10.1016/S0747-7171(85)80028-6},
volume = {1},
year = {1985},
}
@article{4114,
abstract = {Proportional link linkage (PLL) clustering methods are a parametric family of monotone invariant agglomerative hierarchical clustering methods. This family includes the single, minimedian, and complete linkage clustering methods as special cases; its members are used in psychological and ecological applications. Since the literature on clustering space distortion is oriented to quantitative input data, we adapt its basic concepts to input data with only ordinal significance and analyze the space distortion properties of PLL methods. To enable PLL methods to be used when the numbern of objects being clustered is large, we describe an efficient PLL algorithm that operates inO(n 2 logn) time andO(n 2) space},
author = {Day,William H and Herbert Edelsbrunner},
journal = {Journal of Classification},
number = {2-3},
pages = {239 -- 254},
publisher = {Springer},
title = {{Investigation of Proportional Link Linkage Clustering Methods}},
doi = {10.1007/BF01908077},
volume = {2},
year = {1985},
}
@inproceedings{4241,
author = {Curtis,C. F and Curtis,J. and Nicholas Barton},
publisher = {Liss},
title = {{Methodology for testing the hypothesis of single locus control of host resistance to infection and malignancy}},
volume = {3},
year = {1985},
}
@inproceedings{4122,
abstract = {Computational geometry, considered a subfield of computer science, is concerned with the computational aspects of geometric problems. The increasing activity in this rather young field made it split into several reasonably independent subareas. This paper presents several key-problems of the classical part of computational geometry which exhibit strong interrelations. A unified view of the problems is stressed, and the general ideas behind the methods that solve them are worked out.},
author = {Herbert Edelsbrunner},
pages = {1 -- 13},
publisher = {Springer},
title = {{Key-problems and key-methods in computational geometry}},
doi = {10.1007/3-540-12920-0_1},
volume = {166},
year = {1984},
}
@article{4123,
abstract = {Windowing a two-dimensional picture means to determine those line segments of the picture that are visible through an axis-parallel window. A study of some algorithmic problems involved in windowing a picture is offered. Some methods from computational geometry are exploited to store the picture in a computer such that (1) those line segments inside or partially inside of a window can be determined efficiently, and (2) the set of those line segments can be maintained efficiently while the window is moved parallel to a coordinate axis and/or it is enlarged or reduced.},
author = {Herbert Edelsbrunner and Overmars, Mark H and Seidel, Raimund},
journal = {Computer Vision, Graphics, and Image Processing},
number = {1},
pages = {92 -- 108},
publisher = {Academic Press},
title = {{Some methods of computational geometry applied to computer graphics}},
doi = {10.1016/0734-189X(84)90142-7},
volume = {28},
year = {1984},
}
@inproceedings{3513,
author = {Dobkin, David P and Herbert Edelsbrunner},
pages = {88 -- 99},
publisher = {Teubner},
title = {{Ham-sandwich theorems applied to intersection problems}},
year = {1984},
}
@article{4117,
author = {Herbert Edelsbrunner and van Leeuwen,Jan and Ottmann,Thomas and Wood, Derick},
journal = {Rairo-Informatique Theorique Et Applications-Theoretical Informatics and Applications},
number = {2},
pages = {171 -- 183},
publisher = {Cambridge University Press},
title = {{Computing the connected components of simple rectilinear geometrical objects in D-Space}},
volume = {18},
year = {1984},
}
@article{4118,
abstract = {A rectilinear polygon can be viewed as an art gallery room whose walls meet at right angles. An algorithm is presented that stations guards in such a room so that every interior point is visible to some guard. The algorithm partitions the polygon into L-shaped pieces, a subclass of star-shaped pieces, and locates one guard within each kernel. The algorithm runs in O(n log n) time in the worst case for a polygon of n vertices.},
author = {Herbert Edelsbrunner and O'Rourke, Joseph and Welzl, Emo},
journal = {Computer Vision, Graphics, and Image Processing},
number = {2},
pages = {167 -- 176},
publisher = {Academic Press},
title = {{Stationing guards in rectilinear art galleries}},
doi = {10.1016/S0734-189X(84)80041-9},
volume = {27},
year = {1984},
}
@article{4125,
abstract = {Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.
An algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices.},
author = {Aurenhammer,Franz and Herbert Edelsbrunner},
journal = {Pattern Recognition},
number = {2},
pages = {251 -- 257},
publisher = {Springer},
title = {{An optimal algorithm for constructing the weighted Voronoi diagram in the plane}},
doi = {10.1016/0031-3203(84)90064-5},
volume = {17},
year = {1984},
}
@article{4327,
author = {Nicholas Barton and Charlesworth, Brian},
journal = {Annual Review of Ecology and Systematics},
pages = {133 -- 164},
publisher = {Annual Reviews},
title = {{Genetic revolutions, founder effects, and speciation}},
doi = {10.1146/annurev.es.15.110184.001025},
volume = {15},
year = {1984},
}
@inproceedings{4119,
author = {Herbert Edelsbrunner and Welzl, Emo},
pages = {265 -- 272},
publisher = {Springer},
title = {{Monotone edge sequences in line arrangements and applications}},
doi = {10.1007/BFb0030307},
volume = {176},
year = {1984},
}
@article{4121,
abstract = {Whenevern objects are characterized by a matrix of pairwise dissimilarities, they may be clustered by any of a number of sequential, agglomerative, hierarchical, nonoverlapping (SAHN) clustering methods. These SAHN clustering methods are defined by a paradigmatic algorithm that usually requires 0(n 3) time, in the worst case, to cluster the objects. An improved algorithm (Anderberg 1973), while still requiring 0(n 3) worst-case time, can reasonably be expected to exhibit 0(n 2) expected behavior. By contrast, we describe a SAHN clustering algorithm that requires 0(n 2 logn) time in the worst case. When SAHN clustering methods exhibit reasonable space distortion properties, further improvements are possible. We adapt a SAHN clustering algorithm, based on the efficient construction of nearest neighbor chains, to obtain a reasonably general SAHN clustering algorithm that requires in the worst case 0(n 2) time and space.
Whenevern objects are characterized byk-tuples of real numbers, they may be clustered by any of a family of centroid SAHN clustering methods. These methods are based on a geometric model in which clusters are represented by points ink-dimensional real space and points being agglomerated are replaced by a single (centroid) point. For this model, we have solved a class of special packing problems involving point-symmetric convex objects and have exploited it to design an efficient centroid clustering algorithm. Specifically, we describe a centroid SAHN clustering algorithm that requires 0(n 2) time, in the worst case, for fixedk and for a family of dissimilarity measures including the Manhattan, Euclidean, Chebychev and all other Minkowski metrics.},
author = {Day,William H and Herbert Edelsbrunner},
journal = {Journal of Classification},
number = {1},
pages = {7 -- 24},
publisher = {Springer},
title = {{Efficient algorithms for agglomerative hierarchical clustering methods}},
doi = {10.1007/BF01890115},
volume = {1},
year = {1984},
}
@article{3667,
abstract = {Populations of the grasshopper Podisma pedestris were collected from two ends of a zone of hybridization between two chromosome races, at Seyne and Tende in southern France. 21 enzyme and protein loci were detected by gel electrophoresis. Six of these loci showed widespread polymorphism, and a further eleven had very little or no variation. Two loci (Idh, 6Pgd) had rare alleles in different frequencies in the two areas surveyed. The remaining two loci (Mdh-1, Mdh-2) showed a marked increase in the frequency of rare variants, from 1 per cent outside the hybrid zone, up to 5 per cent at its centre. This region of increased electrophoretic variation coincided with the chromosomal cline between the two races, and with a region of decreased viability. It was spread over about the same width as the chromosomal cline. Possible explanations for this extra variation include intragenic recombination and elevated mutation rates.},
author = {Nicholas Barton and Halliday, Bruce and Hewitt, Godfrey M},
journal = {Heredity},
number = {2},
pages = {139 -- 146},
publisher = {Nature Publishing Group},
title = {{Rare electrophoretic variants in a hybrid zone}},
doi = {10.1038/hdy.1983.15},
volume = {50},
year = {1983},
}
@article{4127,
abstract = {The study begun in Part I is completed by providing an algorithm which reports all intersecting pairs of a set of rectangles in d dimensions. This approach yields a solution which is optimal in time and space for planar rectangles and reasonable in higher dimensions.},
author = {Herbert Edelsbrunner},
journal = {International Journal of Computer Mathematics},
number = {3-4},
pages = {221 -- 229},
publisher = {Taylor & Francis},
title = {{A new approach to rectangle intersections part 2}},
doi = {10.1080/00207168308803365},
volume = {13},
year = {1983},
}
@misc{4329,
author = {Nicholas Barton},
booktitle = {Animal Behaviour},
number = {2},
pages = {626 -- 627},
publisher = {Elsevier},
title = {{The extended phenotype: the gene as the unit of selection (review of Dawkins R 1982)}},
doi = {10.1016/S0003-3472(83)80100-6},
volume = {31},
year = {1983},
}