ISSN:
1436-5057
Keywords:
Systolic algorithm
;
computational geometry
;
systolic array
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Die neueren Entwicklungen, die zu parallelen Rechnerarchitekturen führen, haben die Aufmerksamkeit auf das Gebiet der parallelen “Computational Geometry” gelenkt. In diesem Artikel wird das Hauptaugenmerk auf systolische Algorithmen für diesen Themenkreis gerichtet. Es wird ein Überblick über derartige Algorithmen gegeben. Es zeigt sich, daß die meisten grundlegenden geometrischen Probleme mit eindimensionalen systolischen Arrays, wie sie von Kung et al. eingeführt wurden, in Linearzeit gelöst werden können. Eine Reihe neuer Ergebnisse wird vorgestellt, und offene Probleme werden angesprochen.
Notes:
Abstract With the recent development of a rich variety of parallel computer architectures, much attention has been paid to the study of parallel computational geometry. In this paper we put the focus on systolic computational geometry algorithms among those algorithms being developed rapidly in recent years for the various kinds of parallel processors. Our paper gives a survey of recent studies on systolic computational geometry algorithms We show that most of the fundamental geometrical problems can be solved in linear-time by conventional one-dimensional systolic arrays proposed by Kung et al. This paper also includes many new results and some open problems for which we have no linear-time systolic algorithms.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02238727
