Parallel computational geometry of rectangles |
| |
Authors: | Sharat Chandran Sung Kwon Kim 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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|