Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Efficient Robust Digital Hyperplane Fitting with Bounded Error
verfasst von : Dror Aiger, Yukiko Kenmochi, Hugues Talbot, Lilian Buzer
Erschienen in: Discrete Geometry for Computer Imagery
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the following fitting problem: given an arbitrary set of
N
points in a bounded grid in dimension
d
, find a digital hyperplane that contains the largest possible number of points. We first observe that the problem is 3SUM-hard in the plane, so that it probably cannot be solved exactly with computational complexity better than
O
(
N
2
), and it is conjectured that optimal computational complexity in dimension
d
is in fact
O
(
N
d
). We therefore propose two approximation methods featuring linear time complexity. As the latter one is easily implemented, we present experimental results that show the runtime in practice.