Efficient Algorithms for Maximum Regression Depth |
| |
Authors: | Marc van Kreveld Joseph S B Mitchell Peter Rousseeuw Micha Sharir Jack Snoeyink Bettina Speckmann |
| |
Institution: | 1. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands 2. Department of Applied Mathematics and Statistics, SUNY Stony Brook, Stony Brook, USA 3. Department of Mathematics and Computer Science, Universitaire Instelling Antwerpen, Antwerpen, Belgium 4. School of Computer Science, Tel Aviv University, Tel Aviv, Israel 5. Department of Computer Science, UNC Chapel Hill, Chapel Hill, USA 6. Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands
|
| |
Abstract: | We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n
d
) time and O(n
d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2
n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, 2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric
and algorithmic results.
A preliminary version of this paper appeared in the proceedings of the 15th Annual ACM Symposium on Computational Geometry
(1999)
M. van Kreveld partially funded by the Netherlands Organization for Scientific Research (NWO) under FOCUS/BRICKS grant number
642.065.503.
J.S.B. Mitchell’s research largely conducted while the author was a Fulbright Research Scholar at Tel Aviv University. The
author is partially supported by NSF (CCR-9504192, CCR-9732220), Boeing, Bridgeport Machines, Sandia, Seagull Technology,
and Sun Microsystems.
M. Sharir supported by NSF Grants CCR-97-32101 and CCR-94-24398, by grants from the U.S.–Israeli Binational Science Foundation,
the G.I.F., the German–Israeli Foundation for Scientific Research and Development, and the ESPRIT IV LTR project No. 21957
(CGAL), and by the Hermann Minkowski—MINERVA Center for Geometry at Tel Aviv University.
J. Snoeyink supported in part by grants from NSERC, the Killam Foundation, and CIES while at the University of British Columbia. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|