Optimal algorithm for hyperplane depth in the plane

Stefan Langerman, William Steiger

Research output: Contribution to conferencePaper

9 Scopus citations

Abstract

Given a set of n hyperplanes hl,.... hn ε Rd the hyperplane depth of a point P ε Rd is the minimum number of hyperplanes that a ray from P can meet. The hyperplane depth of the arrangement is the maximal depth of points P not in any hi. We give an optimal O(n log n) deterministic algorithm to compute the hyperplane depth of an arrangement in dimension d = 2.

Original languageEnglish (US)
Pages54-59
Number of pages6
StatePublished - Jan 1 2000
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000

Other

Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA
Period1/9/001/11/00

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Optimal algorithm for hyperplane depth in the plane'. Together they form a unique fingerprint.

  • Cite this

    Langerman, S., & Steiger, W. (2000). Optimal algorithm for hyperplane depth in the plane. 54-59. Paper presented at 11th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, .