A Practical Algorithm for Enumerating Collinear Points

This paper studies the problem of enumerating all maximal collinear subsets of size at least three in a given set of \(n\) points. An algorithm for this problem, besides solving degeneracy testing and the exact fitting problem, can also help with other problems, such as point line cover and general...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2017-06
Main Authors: Ali Gholami Rudi, Rufai, Raimi Ayinde
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Parallel processing
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper studies the problem of enumerating all maximal collinear subsets of size at least three in a given set of \(n\) points. An algorithm for this problem, besides solving degeneracy testing and the exact fitting problem, can also help with other problems, such as point line cover and general position subset selection. The classic \emph{topological sweeping} algorithm of Edelsbrunner and Guibas can find these subsets in \(O(n^2)\) time in the dual plane. We present an alternative algorithm that, although asymptotically slower than their algorithm in the worst case, is simpler to implement and more amenable to parallelization. If the input points are decomposed into \(m\) convex polygons, our algorithm has time complexity \(O(n^2 \log m)\) and space complexity \(O(n)\). Our algorithm can be parallelized on the CREW PRAM with time complexity \(O(n \log m)\) using \(n\) processors.
ISSN:2331-8422