Title :
Geometric data structures on a reconfigurable mesh, with applications
Author_Institution :
Dept. of Math. Stat. & Comput. Sci., New England Univ., Armidale, NSW, Australia
Abstract :
We present several geometric data structures and algorithms for problems for a planar set of rectangles and bipartitioning problems for a point set in two dimensions on a reconfigurable mesh of size n×n. The problems for rectangles include computing the measure, contour perimeter and maximum clique for the union of a set of rectangles. The bipartitioning problems for a two dimensional point set are solved in the L∞ and L1 metrics. We solve all these problems in O(log n) time
Keywords :
computational complexity; computational geometry; data structures; multiprocessor interconnection networks; parallel algorithms; parallel architectures; reconfigurable architectures; O(log n) time; bipartitioning; contour perimeter; geometric data structures; maximum clique; measure; planar set of rectangles; point set; reconfigurable mesh; Computer architecture; Concurrency control; Data structures; Mathematics; Parallel architectures; Pattern recognition; Spatial databases; Statistics; Tree data structures; Very large scale integration;
Conference_Titel :
Parallel Processing Symposium, 1997. Proceedings., 11th International
Conference_Location :
Genva
Print_ISBN :
0-8186-7793-7
DOI :
10.1109/IPPS.1997.580983
