# Fast O_{expected}(N) Algorithm for Finding Exact Maximum Distance in E^2 Instead of O(N^2) or O(N lg N)

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Aug 2022.

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

- [Hallucination Detection: A Probabilistic Framework Using Embeddings Distance Analysis](https://mlsanity.com/paper/2502.08663/) (2025)

## Abstract (arXiv)

This paper describes novel and fast, simple and robust algorithm with O(N) expected complexity which enables to decrease run-time needed to find an exact maximum distance of two points in E2. The proposed algorithm has been evaluated experimentally on larger different datasets. The proposed algorithm gives a significant speed-up to applications, when medium and large data sets are processed. It is over 10 000 times faster than the standard algorithm for 10^6 points randomly distributed points in E2. Experiments proved the advantages of the proposed algorithm over the standard algorithm and convex hull diameters approaches.