A linear algorithm for eliminating hidden-lines from a polygonal cylinder
type: Item
instance of: scholarly article
title: A linear algorithm for eliminating hidden-lines from a polygonal cylinder
zbMATH Open document ID: 0639.68040
DOI: 10.1007/BF01890987
author: David Rappaport
published in: The Visual Computer
publication date: 1986-01-01T00:00:00Z
review text: A variety of applications have motivated interest in the hidden-line and hidden-surface problem. This has resulted in a number of fundamentally different solutions. However no algorithm has been shown to be optimal. A common trait among algorithms for hidden-line elimination is a worst case complexity of \(O(n^ 2)\). It is the intent here to introduce an algorithm that exhibits a linear worst case complexity. The use of a restricted class of input, has been employed to achieve asymptotic improvement in complexity as well as simplifying the problem enough to permit theoretic analysis of the algorithm. The class of input is still general enough to conform to the requirements of a number of applications.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4043245
zbMATH Keywords: computational geometry
zbMATH Keywords: geometric algorithms
zbMATH Keywords: hidden-line elimination
zbMATH Keywords: worst case complexity
MaRDI profile type: Publication
cites work: Q4091421
cites work: A linear algorithm for computing the visibility polygon from a point
cites work: Finding the convex hull of a simple polygon
cites work: A Solution to the Hidden-Line Problem for Computer-Drawn Polyhedra
cites work: A linear algorithm for finding the convex hull of a simple polygon
cites work: Q3959475
description: scientific article; zbMATH DE number 4043245