Show simple item record

dc.creatorLU, MI
dc.date.accessioned 2007-05-09T19:45:48Z
dc.date.available 2007-05-09T19:45:48Z
dc.date.issued 1987
dc.identifier.urihttps://hdl.handle.net/1911/16090
dc.description.abstract Parallel algorithms to solve several computational geometric problems on mesh-connected computers (MCC's) and systolic arrays are designed and analyzed. We present parallel MCC algorithms to solve the following proximity problems. Given a set of n planar points represented by their Cartesian coordinates, determine the nearest neighbor for each point and find the closest pair of the set. Our algorithms execute on a $\sqrt{n}\times\sqrt{n}$ MCC with constant storage per processor and the time performance is $O(\sqrt{n})$ which is optimal. We also describe parallel algorithm to construct the Voronoi diagram and the minimum spanning tree of a given set of n planar points, and to find the closest pair between two sets on a $\sqrt{n}\times\sqrt{n}$ MCC in $O(\sqrt{n}{\rm log}n)$ time. The best known sequential algorithms for these problems have an optimal $O(n{\rm log}n)$ time complexity. In addition, MCC algorithms for computing several properties of a set of, possibly intersecting rectangles are presented. Given a set of n iso-oriented rectangles, we describe MCC algorithms for determining the area of the logic "OR" of these rectangles, the area of pairwise logic "AND" of the rectangles, the largest number of rectangles that overlap and the minimum separation between any pair of a set of non-overlapping rectangles. All these algorithms can be implemented on a $\sqrt{n}\times\sqrt{n}$ MCC in an optimal $O(\sqrt{n})$ time, and compare favorably with the known sequential algorithms which have $O(n{\rm log}n)$ time complexity. For the above tasks, we also describe methods to solve problems of size n on MCC's with p processors, where $p < n$. Lower bounds on the time complexity are demonstrated and the optimal size of MCC's to be used is derived. Finally, we present systolic algorithms to solve the segment intersection counting problem and to construct the convex hull of a set of planar points, as well as an update algorithm for the fixed size circle placement problem. For a problem of size n, our algorithms use a systolic array of $n\sp{2/3}\times n\sp{2/3}$ cells and have a time complexity of $O(n\sp{2/3})$.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.subjectElectronics
Electrical engineering
dc.title SOLVING COMPUTATIONAL GEOMETRY PROBLEMS ON MESH-CONNECTED COMPUTERS
dc.type.genre Thesis
dc.type.material Text
thesis.degree.department Electrical and Computer Engineering
thesis.degree.discipline Engineering
thesis.degree.grantor Rice University
thesis.degree.level Doctoral
thesis.degree.name Doctor of Philosophy
dc.identifier.citation LU, MI. "SOLVING COMPUTATIONAL GEOMETRY PROBLEMS ON MESH-CONNECTED COMPUTERS." (1987) Diss., Rice University. https://hdl.handle.net/1911/16090.


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record