A VLSI Solution to the Vertical Segment Visibility Problem
- 1 October 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (10) , 923-928
- https://doi.org/10.1109/TC.1986.1676685
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
This publication has 3 references indexed in Scilit:
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979