hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.

Algorithms.Geometry.SmallestEnclosingBall.RIC

Description

An randomized algorithm to compute the smallest enclosing disk of a set of $$n$$ points in $$\mathbb{R}^2$$. The expected running time is $$O(n)$$.

Synopsis

# Documentation

smallestEnclosingDisk' :: (Ord r, Fractional r) => (Point 2 r :+ p) -> (Point 2 r :+ p) -> [Point 2 r :+ p] -> DiskResult p r Source #

Smallest enclosing disk.

smallestEnclosingDisk :: (Ord r, Fractional r, MonadRandom m) => [Point 2 r :+ p] -> m (DiskResult p r) Source #

Compute the smallest enclosing disk of a set of points, implemented using randomized incremental construction.

pre: the input has at least two points.

running time: expected $$O(n)$$ time, where $$n$$ is the number of input points.

smallestEnclosingDiskWithPoint :: (Ord r, Fractional r) => (Point 2 r :+ p) -> NonEmpty (Point 2 r :+ p) -> Maybe (DiskResult p r) Source #

Smallest enclosing disk, given that p should be on it.

smallestEnclosingDiskWithPoints :: (Ord r, Fractional r) => (Point 2 r :+ p) -> (Point 2 r :+ p) -> [Point 2 r :+ p] -> Maybe (DiskResult p r) Source #

Smallest enclosing disk, given that p and q should be on it

running time: $$O(n)$$