# Chan's algorithm

> algorithm for finding the convex hull of a set of points in the plane

**Wikidata**: [Q2025538](https://www.wikidata.org/wiki/Q2025538)  
**Wikipedia**: [English](https://en.wikipedia.org/wiki/Chan's_algorithm)  
**Source**: https://4ort.xyz/entity/chan-s-algorithm

## Summary
Chan's algorithm is a computational method for finding the convex hull of a set of points in the plane, which is the smallest convex polygon enclosing all given points. It's a randomized algorithm with optimal expected time complexity.

## Key Facts
- **Classification**: A type of geometric algorithm, which is a subclass of combinatorial algorithms.
- **Purpose**: Computes the convex hull of a set of points, which is the smallest convex polygon containing all the points.
- **Related Algorithms**: Another method for computing the convex hull in the plane.
- **Time Complexity**: Achieves optimal expected time complexity (O(n log h)).
- **Wikipedia Coverage**: Available in multiple languages including English, French, Japanese, and Russian.
- **Microsoft Academic ID (Discontinued)**: 2781146841
- **Wikidata Description**: "Algorithm for finding the convex hull of a set of points in the plane"

## FAQs
### Q: What is the primary purpose of Chan's algorithm?
A: It computes the convex hull of a set of points, determining the smallest convex polygon that contains all input points.

### Q: What is the time complexity of Chan's algorithm?
A: It achieves optimal expected time complexity of O(n log h), where n is the number of input points and h is the number of hull points.

### Q: What are the real-world applications of Chan's algorithm?
A: Used in computer graphics for collision detection and shape rendering, in robotics for path planning, and in data science for outlier detection.

### Q: How does Chan's algorithm compare to other convex hull algorithms?
A: It's a randomized algorithm with optimal expected time complexity, while other methods like Graham Scan and Gift Wrapping have different computational approaches.

## Why It Matters
Convex hull algorithms are foundational in computational geometry, enabling efficient solutions to problems requiring boundary determination or shape analysis. They play a critical role in fields like computer graphics (e.g., collision detection, shape rendering), robotics (path planning), and data analysis (outlier detection). By providing a minimal enclosing shape, these algorithms optimize computations in spatial queries, pattern recognition, and geometric modeling. Their efficiency and versatility make them indispensable in both theoretical research and practical applications, from game development to scientific simulations.

## Notable For
- **Optimal Expected Complexity**: Achieves optimal expected time complexity (O(n log h)) for convex hull computation.
- **Randomized Approach**: Implements a randomized algorithm for computing convex hulls.
- **Computational Geometry Foundation**: A core tool in computational geometry for shape analysis.
- **Broad Applications**: Used across computer graphics, robotics, and data science domains.

## Body
### Definition and Scope
Chan's algorithm is a computational method designed to compute the convex hull of a set of points in the plane. The convex hull represents the smallest convex polygon that contains all given points, defined as the intersection of all convex sets that include the input points.

### Types of Algorithms
Several algorithms exist for computing convex hulls, each with distinct approaches:
- **Graham Scan**: Sorts points by polar angle and constructs the hull incrementally.
- **Gift Wrapping (Jarvis March)**: Iteratively selects the next hull point by checking all candidates.
- **Chan's Algorithm**: A randomized algorithm with optimal expected time complexity.
- **Kirkpatrick–Seidel Algorithm**: Achieves O(n log h) time by leveraging geometric properties.

### Applications
- **Computer Graphics**: Collision detection, shape rendering, and mesh generation.
- **Robotics**: Path planning and obstacle avoidance.
- **Data Science**: Outlier detection and clustering.
- **Geometric Modeling**: Simplifying complex shapes for analysis.

### Technical Details
- **Input**: A set of points in a plane or higher-dimensional space.
- **Output**: The vertices of the convex hull in order.
- **Complexity**: Ranges from O(n log n) for Graham Scan to O(n log h) for Kirkpatrick–Seidel.

### Related Algorithms
Chan's algorithm belongs to the broader category of convex hull algorithms, which includes:
- **Monotone Chain**: An algorithm for finding the convex hull of planar points.
- **Gift Wrapping Algorithm**: Traces the boundary of the hull to compute it.
- **Kirkpatrick–Seidel Algorithm**: Computes the convex hull in O(n log h) time.
- **Graham Scan**: A widely used algorithm for finding the convex hull of planar points.

### Historical Context
While the exact origin of Chan's algorithm is not specified in the source material, it represents one of several approaches to solving the convex hull problem in computational geometry. The algorithm is part of the broader development of efficient geometric algorithms that have evolved alongside other methods like Graham Scan and Gift Wrapping.</think>

## References

1. Freebase Data Dumps. 2013