# Computational complexity lower bounds of certain discrete Radon transform approximations

arXiv: https://arxiv.org/abs/1801.01054 · HTML: https://mlsanity.com/paper/1801.01054/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2018.

## Built on by (most cited first, 2 of 2)

- [Generalization of Brady-Yong Algorithm for Fast Hough Transform to Arbitrary Image Size](https://mlsanity.com/paper/2411.07351/) (2024)
- [A High-Accuracy Fast Hough Transform with Linear-Log-Cubed Computational Complexity for Arbitrary-Shaped Images](https://mlsanity.com/paper/2509.00231/) (2025)

## Abstract (arXiv)

For the computational model where only additions are allowed, the Omega(n2log n) lower bound on operations count with respect to image size n× n is obtained for two types of the discrete Radon transform implementations: the fast Hough transform and a generic strip pattern class which includes the classical Hough transform, implying the fast Hough transform algorithm asymptotic optimality. The proofs are based on a specific result from the boolean circuits complexity theory and are generalized for the case of boolean vee binary operation.