Finding the Convex Hull of a Simple Polygon,

Abstract

It is well known that the convex hull of a set of n points in the (Euclidean) plane can be found by an algorithm having worst-case complexity O(n log n). In this note we give a short linear algorithm for finding the convex hull in the case that the (ordered) set of points from the vertices of a simple (i.e., non-self-intersecting) polygon. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1981
Accession Number
ADA113420

Entities

People

  • Frances Yao
  • Rondld L. Graham

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computer Graphics
  • Computer Science
  • Computers
  • Data Processing
  • Graphics
  • Hypotheses
  • Information Processing
  • Notation
  • Orientation (Direction)
  • Preprocessing
  • Sequences
  • Theses
  • Universities

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.