Title :
A VLSI Solution to the Vertical Segment Visibility Problem
Author :
Lodi, E. ; Pagli, L.
Author_Institution :
Department of Information Science, University of Pisa
Abstract :
We present a parallel algorithm to solve the visibility problem among n vertical segments in a plane, which can be implemented on a VLSI chip arranged as a mesh of trees. Our algorithm determines all the pairs of segments that "see" each other in time O(log n); while the fastest sequential algorithm requires O(n log n). A lower bound to the area-time complexity of this problem of O(n2 log2 n) is also derived.
Keywords :
Area-time complexity; VLSI; computational geometry; mesh of trees; parallel algorithm; Binary trees; Circuits; Clocks; Compaction; Computational geometry; Information science; Parallel algorithms; Proposals; Very large scale integration; Wire; Area-time complexity; VLSI; computational geometry; mesh of trees; parallel algorithm;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1986.1676685
