Systolic algorithms for rectilinear polygons

DOI10.1016/0010-4485(87)90148-5MaRDI QIDQ1108798zbMATH OpenOpenAlexFDO

Authors Rajiv Kane, Sartaj Sahni

Publication date 1987

Published in CAD. Computer-Aided Design (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0010-4485(87)90148-5

zbMATH Keywords

circuit designoversizingrectilinear polygonssystolic algorithmsundersizingVLSI

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Algorithms in computer science (68W99)

Review text

We develop systolic algorithms for the OR, AND, oversizing, and undersizing of rectilinear polygons. These algorithms work on an edge representation of the polygons rather than on a bit map representation. The algorithms are to be run on a systolic chain of processors. The edges are input at the left end of this chain. From here, they ``float as far to the right as necessary. As edges float to the right, they compare themselves with edges that are resident in the processors they are floating through. During this comparison the output polygons are generated. Output polygons float to the left. These polygons are output from the left end of the chain. The throughput of the systolic system can be improved by increasing the length of the processor chain.

Recommendations

• Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region
• Systolic algorithms for computational geometry problems - a survey
• Computational geometry algorithms for the systolic screen
• Optimal parallel algorithms for rectilinear link-distance problems
• The contour problem for rectilinear polygons

Cited in

(2)

• Systolic algorithms for computing the visibility polygon and triangulation of a polygonal region
• Systolic algorithms for computational geometry problems - a survey

This page was built for publication: Systolic algorithms for rectilinear polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108798)