ISSN:
1436-5057
Keywords:
52.A30
;
52.A10
;
Visibility
;
simple polygon
;
convex hull
;
triangulation
;
L-convex polygon
;
edge visible polygon
;
geometric complexity
;
algorithms
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Kürzlich haben ElGindy und Avis (EA) einenO(n)-Algorithmus zur Lösung des Problems der verdeckten Linien in einem überschneidungsfreien Polygon vorgelegt. Hier zeigen wir, daß ihr Algorithmus auch zur Lösung anderer geometrischer Probleme verwendet werden kann. Insbesondere können wir einL-konvexes Polygon in der ZeitO(n) triangulieren und die konvexe Hülle eines überschneidungsfreien Polygons in der gleichen Zeit finden. Ferner kann die Überprüfung eines überschneidungsfreien Polygons aufL-Konvexität in der ZeitO (n2) erfolgen.
Notes:
Abstract Recently ElGindy and Avis (EA) presented anO(n) algorithm for solving the two-dimensional hidden-line problem in ann-sided simple polygon. In this paper we show that their algorithm can be used to solve other geometric problems. In particular, triangulating anL-convex polygon and finding the convex hull of a simple polygon can be accomplished inO(n) time, whereas testing a simple polygon forL-convexity can be done inO(n 2) time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02263430
Permalink
