Enumerating Collinear Points in Higher Dimensions
| Autor: | Ali Gholami Rudi, Raimi Ayinde Rufai |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: | |
| Zdroj: | Scientific Annals of Computer Science, Vol XXIX, Iss 1, Pp 81-100 (2019) |
| Druh dokumentu: | article |
| ISSN: | 1843-8121 2248-2695 |
| DOI: | 10.7561/SACS.2019.1.81 |
| Popis: | In this paper, we study the problem of reporting all maximal collinear subsets of a point set $S$ in $\mathbb{R}^d$ for $d \ge 3$. An algorithm for this problem can be used to detect if any three of the points are collinear or find the line that intersects the most points in $S$. Besides, obtaining such maximal subsets is necessary for some problems about the collinearity relation among points, such as when covering them with the fewest lines. We present practical algorithms to find all maximal collinear subsets of a set of $n$ points, including one with space complexity $O(n)$ and time complexity $O(dn^2 \log n)$, and one with space complexity $O(n^2)$ and time complexity $O(d^2n^2)$. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|