Title :
Point visibility of a simple polygon on reconfigurable mesh
Author :
Kim, Hong-Geun ; Cho, Yoo-Kun
Author_Institution :
Dept. of Comput. Eng., Seoul Nat. Univ., South Korea
Abstract :
We consider the following problem. Given a point z in the interior of a simple polygon P with n vertices, find all the boundary points of P that are "visible" from z. We present two parallel algorithms for this problem on a two dimensional reconfigurable mesh. The first algorithm runs in O(log2 n) timing using n1/2 processors, and the second one runs in O(1) time using n × n processors
Keywords :
computational complexity; computational geometry; multiprocessor interconnection networks; parallel algorithms; reconfigurable architectures; boundary points; parallel algorithms; point visibility; simple polygon; two dimensional reconfigurable mesh; Broadcasting; Parallel algorithms; Phase change random access memory; Switches;
Conference_Titel :
Parallel and Distributed Processing, 1993. Proceedings of the Fifth IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-4222-X
DOI :
10.1109/SPDP.1993.395457
