• Libraries
    • Log in to:
    View Item 
    •   MSpace Home
    • Faculty of Graduate Studies (Electronic Theses and Practica)
    • FGS - Electronic Theses and Practica
    • View Item
    •   MSpace Home
    • Faculty of Graduate Studies (Electronic Theses and Practica)
    • FGS - Electronic Theses and Practica
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Computing batched depth queries and the depth of a set of points

    Thumbnail
    View/Open
    Thesis (1.569Mb)
    Date
    2022-08-19
    Author
    Rajapakse, Sachini Kanchana
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1993/36716
    Collections
    • FGS - Electronic Theses and Practica [25522]

    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, ...

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     

    Browse

    All of MSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Login

    Statistics

    View Usage Statistics

    DSpace software copyright © 2002-2016  DuraSpace
    Contact Us | Send Feedback
    Theme by 
    Atmire NV