Minimum Covering Ellipses
SIAM Journal on Scientific and Statistical ComputingPublished 1 December 1980
B. W. Silverman, D. M. Titterington
Citations71
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An exact terminating algorithm is developed for finding the ellipse of smallest area covering a given plane point set with the aid of a duality relation originally obtained in the theory of statistical experimental design.
Abstract
With the aid of a duality relation originally obtained in the theory of statistical experimental design, an exact terminating algorithm is developed for finding the ellipse of smallest area covering a given plane point set. Some applications and related problems are discussed. Empirical timings show the algorithm to be highly efficient, particularly for large sets of points.
Keywords
Computer ScienceDecision SciencesEngineering
Closest-point problems
1,062 Citations1975Michael Ian Shamos, Dan Hoey
The purpose of this paper is to introduce a single geometric structure, called the Voronoi diagram, which can be constructed rapidly and contains all of the relevant proximity information in only linear space, and is used to obtain O(N log N) algorithms for most of the problems considered.
Journal of the ACMOn the Average Number of Maxima in a Set of Vectors and Applications
369 Citations1978Jon Bentley, H. T. Kung +2 more
A recurrence relation is derived for computing the average number of maxunal vectors m a set of n vectors m d-space under the assumpUon that all (nl) a relative ordermgs are equally probable.
Transportation ScienceGeometrical Solutions for Some Minimax Location Problems
347 Citations1972Jack Elzinga, Donald W. Hearn
ACM Transactions on Mathematical SoftwareA New Convex Hull Algorithm for Planar Sets
285 Citations1977William F. Eddy
A new algorithm, CONVEX, that determines which points of a planar set are vertices of the convex hull of the set is presented and it is shown thatCONVEX operates in a fashion similar to the sorting algorithm QUICKERSORT.
Management ScienceThe Minimum Covering Sphere Problem
184 Citations1972D. Jack Elzinga, Donald W. Hearn
A finite decomposition algorithm, based on the Simplex method of quadratic programming, is developed for which computer storage requirements are independent of the number of points and computing time is approximately linear in the numberof points.
Journal of the Royal Statistical Society Series B (Statistical Methodology)Order Invariant Methods for Data Analysis
143 Citations1972Robin Sibson
This paper investigates order invariance criteria which can be applied to methods for analysing measures of pairwise similarity or dissimilarity, and applies these criteria to method for classification, scaling, and sequencing.
Journal of Applied ProbabilitySur L'enveloppe convexe des nuages de points aleatoires dans <i>R<sup>n</sup></i>. I
138 Citations1970Henri-François Raynaud
Journal of the Royal Statistical Society Series C (Applied Statistics)Estimation of Correlation Coefficients by Ellipsoidal Trimming
116 Citations1978D. M. Titterington
Information Processing LettersDivide and conquer for linear expected time
116 Citations1978Jon Bentley, Michael Ian Shamos
BiometrikaOptimal design: Some geometrical aspects of D-optimality
106 Citations1975D. M. Titterington
BiometrikaA geometric approach to optimal design theory
99 Citations1973S. D. Silvey, D. M. Titterington
Journal of Mathematical Analysis and ApplicationsPattern separation by convex programming
83 Citations1965J. B. Rosen
It is shown that the pattern separation problem can be formulated and solved as a conveX pro gramming problem, i.e., the minimization of a convex function subject to linear constraints.
The Computer JournalConstructing the convex hull of a set of points in the plane
67 Citations1979P. J. Green
Transportation ScienceMinimax Multifacility Location with Euclidean Distances
66 Citations1976Jack Elzinga, Donald W. Hearn +1 more
Naval Research Logistics QuarterlyOptimal location of a single service center of certain types
44 Citations1971K. P. K. Nair, R. Chandrasekaran
It is seen that for a class of problems, the geometric method is well suited and very efficient while the graph theoretic method, in general, will give only approximate solutions in spite of the increased efforts involved.
Naval Research Logistics QuarterlyThe minimum sphere covering a convex polyhedron
16 Citations1974Jack Elzinga, Donald W. Hearn