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 language | English (US) |
|---|---|
| Pages (from-to) | 191-202 |
| Number of pages | 12 |
| Journal | Computing |
| Volume | 31 |
| Issue number | 3 |
| DOIs | |
| State | Published - 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