Parallel computational geometry of rectangles |
| |
Authors: | Sharat Chandran Sung Kwon Kim and David M Mount |
| |
Affiliation: | (1) Center for Automation Research, University of Maryland, 20742 College Park, MD, USA;(2) Department of Computer Science, University of Washington, 98195 Seattle, WA, USA;(3) Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, 20742 College Park, MD, USA |
| |
Abstract: | Rectangles in a plane provide a very useful abstraction for a number of problems in diverse fields. In this paper we consider the problem of computing geometric properties of a set of rectangles in the plane. We give parallel algorithms for a number of problems usingn processors wheren is the number of upright rectangles. Specifically, we present algorithms for computing the area, perimeter, eccentricity, and moment of inertia of the region covered by the rectangles inO(logn) time. We also present algorithms for computing the maximum clique and connected components of the rectangles inO(logn) time. Finally, we give algorithms for finding the entire contour of the rectangles and the medial axis representation of a givenn × n binary image inO(n) time. Our results are faster than previous results and optimal (to within a constant factor).The work of Sung Kwan Kim was supported by NSF Grant CCR-87-03196 and the work of D. M. Mount was partially supported by National Science Foundation Grant CCR-89-08901. |
| |
Keywords: | Orthogonal plane-sweep Medial axis transform Picture processing Computer vision |
本文献已被 SpringerLink 等数据库收录! |
|