Computing batched depth queries and the depth of a set of points
Abstract
In Computational Geometry and Statistics, we often encounter problems related
to data depth. Data depth describes the centrality of an object relative to a set of
objects. Simplicial depth and Tukey depth are two such common depth measures for
expressing the depth of a point q relative to a set P of points in R^d. In this thesis,
we discuss the problems of how efficiently we can compute the depths of k query
points in a batch relative to a set P of n points. We examine three algorithms for
computing batched simplicial depth queries and two algorithms to compute batched
Tukey depth queries in R^2. Depending on the relative cardinalities of P and Q, one
algorithm performs better than others for each depth measure. Then, we introduce
new notions to express the depth of a set Q of points relative to a set P of points in R^d
as the average depth of points in Q. We discuss how to compute these new notions of
depth in R^2 by applying the algorithms above, giving an algorithm for computing the
simplicial depth of a set Q relative to set P in O(min{kn log n, n^2+nk, n^4+k log n})
time, and the Tukey depth of a set Q relative to set P in O(min{kn log n, n^2 +
k log n}) time, when n = |P| and k = |Q|. Further, we consider different statistical
and probabilistic interpretations of these new notions of depth of a set. We show
that the simplicial depth of Q relative to P is proportional to the expected number of
points of Q contained in a simplex constructed from points selected randomly from
P. Properties of depth measures are commonly analyzed to compare and contrast
different depth measures, which are initially introduced for the depth measures of
a single query point; we present generalizations for five of these properties for the
depth measures of sets and evaluate these properties to compare depth measures
defined for a set of points.
Collections
Related items
Showing items related by title, author, creator and subject.
-
Effect of tillage on recruitment depth of five weed species measured in situ in zero and conventional tillage fields in Manitoba
Du Croix Sissons, Michelle J. (1999-07-01)Knowing the depth of weed seedling recruitment and how tillage affects the depth of recruitment can help in the development of improved weed control methods. Weed seedling recruitment depth is a better measure of seed ... -
Projected Climate Impacts on Snow Depths and Discharges In the Lake Winnipeg Watershed
Dibike, Yonas B.; Prowse, Terry; Shrestha, Rajesh; Thompson, Morgan (Government of Canada, Environment Canada, 2011)A number of studies have documented recent trends toward earlier spring snowmelt (e.g. Brown, 2000) and a decline in snow cover extent (Dery and Brown, 2007) across many regions of the Northern Hemisphere in response to ... -
Implementation of a fuzzy logic based seeding depth control system
Tessier, Thomas R. (1997-01-20)Imprecise seeding depth can lead to lower crop yields and increased power requirements. For example, a variation of 2.56 cm (1 inch) from optimum depth results in 45%, 25%, and 15% reduction in the emergence of soybeans, ...