Computational Geometry on a Systolic Chip
- 1 September 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (9) , 774-785
- https://doi.org/10.1109/TC.1984.1676494
Abstract
This paper describes systolic algorithms for a number of geometric problems. For the sake of realism we restrict our investigation to one-dimensional arrays whose communication links with the outside are located at the end cells. Implementations yielding maximal throughput are given for solving dynamic versions of convex hull, inclusion, range and intersection search, planar point location, intersection, triangulation, and closest-point problems.Keywords
This publication has 18 references indexed in Scilit:
- A New Approach to Planar Point LocationSIAM Journal on Computing, 1981
- A Systolic Data Structure Chip for Connectivity ProblemsPublished by Springer Nature ,1981
- A combinatorial limit to the computing power of V.L.S.I. circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1980
- The Design of Special-Purpose VLSI ChipsComputer, 1980
- Transforming static data structures to dynamic structuresPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- An optimal real-time algorithm for planar convex hullsCommunications of the ACM, 1979
- Finding the intersection of n half-spaces in time O(n log n)Theoretical Computer Science, 1979
- Triangulating a simple polygonInformation Processing Letters, 1978
- Geometric intersection problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- On the identification of the convex hull of a finite set of points in the planeInformation Processing Letters, 1973