Output-sensitive results on convex hulls, extreme points, and related problems

Research output: Contribution to journalArticlepeer-review

Abstract

We use known data structures for ray-shooting and linear-programming queries to derive new output-sensitive results on convex hulls, extreme points, and related problems We show that the f-face convex hull of an n-point set P in a fixed dimension d ≥ 2 can be constructed in O(n log f + (nf)1-1/([d/2+1) logO(1) time; this is optimal if f = O(n1/[D/2J / log K n) for some sufficiently large constant K. We also show that the h extreme points of P can be computed in O(n logO(1) h-(nh)1-1/([d/2+1) logO(1)n) time These results are then applied to produce an algorithm that computes the vertices of all the convex layers of P in O(n2-γ) time for any constant γ < 2/([d/2]2 + 1). Finally, we obtain improved time bounds for other problems including levels in arrangements and linear programming with few violated constraints. In all of our algorithms the input is assumed to be in general position.

Original languageEnglish (US)
Pages (from-to)369-387
Number of pages19
JournalDiscrete and Computational Geometry
Volume16
Issue number4
DOIs
StatePublished - Dec 1996
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Output-sensitive results on convex hulls, extreme points, and related problems'. Together they form a unique fingerprint.

Cite this