Applications of a two-dimensional hidden-line algorithm to other geometric problems

H. ElGindy, D. Avis, G. Toussaint

Research output: Contribution to journalArticle

Abstract

Recently ElGindy and Avis (EA) presented an O(n) algorithm for solving the two-dimensional hidden-line problem in an n-sided simple polygon. In this paper we show that their algorithm can be used to solve other geometric problems. In particular, triangulating an L-convex polygon and finding the convex hull of a simple polygon can be accomplished in O(n) time, whereas testing a simple polygon for L-convexity can be done in O(n2) time.

Original languageEnglish (US)
Pages (from-to)191-202
Number of pages12
JournalComputing
Volume31
Issue number3
DOIs
StatePublished - Sep 1983

Keywords

  • AMS Subject Classifications: 52.A30, 52.A10
  • L-convex polygon
  • Visibility
  • algorithms
  • convex hull
  • edge visible polygon
  • geometric complexity
  • simple polygon
  • triangulation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Applications of a two-dimensional hidden-line algorithm to other geometric problems'. Together they form a unique fingerprint.

  • Cite this