Finding the vertices of the convex hull, even unordered, takes Omega(n log n) time -- a proof by reduction from epsilon-closeness

2018/12/04 by Herman Haverkort, Haverkort, Herman
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1812.01332

openalex publication_date 2018/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of computing, given a set S of n points in the plane, which points of S are vertices of the convex hull of S. For certain variations of this problem, different proofs exist that the complexity of this problem in the algebraic decision tree model is Omega(n log n). This paper provides a relatively simple proof by reduction from epsilon-closeness.

Related

• Convex hulls of finite sets of points in two and three dimensions
• Computing the Approximate Convex Hull in High Dimensions
• Fast and Exact Convex Hull Simplification
• A Combinatorial Proof of Universal Optimality for Computing a Planar Convex Hull
• The computational complexity of convex bodies