In this paper, we first report an O(1) time algorithm to Visibility problems are investigated using reconfigurable solve the visibility problem in the plane containing a total meshes. A number of algorithms are proposed on the architecof n disjoint edges using an n ฯซ n R-mesh. Thus, the ture for visibility computation in two and three dimensions. algorithm is asymptotically the fastest. Moreover, our visi-We show that visibility of a total of n disjoint edges in the bility algorithm is AT 2 optimal in the word model of VLSI, plane can be computed in O(1) time on an n ุ n mesh. The meaning that the same time bound cannot be achieved by result is optimal in the word model of VLSI. For the case that using a processor array smaller than n ฯซ n. We also conthe edges are not disjoint, the problem is shown to be solvable sider the case that the edges are permitted to intersect in O(1) time by using a mesh of slightly larger size or in slightly with each other. In this case, the computation required is more time on an n ุ n mesh. We also present hidden-line and surface elimination algorithms that run on an n ุ n ุ n mesh slightly higher than that for disjoint edges. Next, a hidden for a set of disjoint triangles in 3-space containing a total of n line elimination algorithm is presented that runs in O( ) vertices in O(1) time and O(k) time, respectively, where 0 ี
time on a 3-dimensional R-mesh (i.e., n ฯซ n ฯซ n R-mesh).
k ฯฝ n is an output-dependent parameter.