Hardware-assisted computation of depth contours

Shankar Krishnan, Nabil H. Mustafa, Suresh VenkatasubramanianSODA 2002 · OpenReview

Abstract

Given a set of points P in the plane, the location depth of a point u is the minimum number of points of P lying in a closed halfplane defined by a line through u. The set of all points in the plane having location depth at least k is called the depth contour of depth k. In this paper, we present an algorithm that makes extensive use of modern graphics architectures to compute the approximate depth contours of a set of points. The output of our algorithm presents the contours as a coloring of each point with its depth value, as opposed to computing the geometric description of the contour boundary. Our algorithm performs significantly better than currently known implementations, outperforming them by at least one order of magnitude and having a strictly better asymptotic growth rate.
BibTeX
@inproceedings{krishnan2002hardware,
  author = {Shankar Krishnan and Nabil H. Mustafa and Suresh Venkatasubramanian},
  title = {{Hardware-assisted computation of depth contours}},
  booktitle = {SODA},
  year = {2002},
  url = {https://openreview.net/forum?id=3GkEP4KU3f},
}

Loading related content...

Figure