A lower bound on the complexity of the convex hull problem for simple polyhedra

DOI10.1016/0020-0190(87)90126-8zbMath0653.68029OpenAlexW2076987370MaRDI QIDQ1107997

Andrew Klapper

Publication date: 1987

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90126-8

zbMATH Keywords

convex hulllower boundcomputational geometrygeometric complexitysimple polyhedron

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Convex sets in (3) dimensions (including convex surfaces) (52A15)

Related Items

A global optimization RLT-based approach for solving the hard clustering problem ⋮ A global optimization RLT-based approach for solving the fuzzy clustering problem

Cites Work

• A linear algorithm for finding the convex hull of a simple polygon
• An efficient algorithm for determining the convex hull of a finite planar set
• On finding the convex hull of a simple polygon
• Convex hulls of finite sets of points in two and three dimensions
• Finding the convex hull of a simple polygon