hgeometry-0.12.0.4: Geometric Algorithms, Data structures, and Data types.
Copyright(C) Frank Staals
Licensesee the LICENSE file
MaintainerFrank Staals
Safe HaskellNone
LanguageHaskell2010

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)\)