Cumincad : CUMINCAD Papers : Search Results

Hits 1 to 2 of 2

_id	a4cc
authors	Hunter, Gregory M. and Steiglitz, Kenneth
year	1979
title	Operations on Images Using Quad Trees
source	IEEE Transactions on Pattern Analysis and Machine Intelligence. April, 1979. vol. PAMI-1: pp. 145-153 : ill. includes bibliography
summary	A quad tree for representing a picture is a tree in which successively deeper levels represent successively finer subdivisions of picture area. An algorithm is given for superposing N quad trees in time proportional to the total number of nodes in the trees. Warnock-type algorithms are then presented for building the quad tree for the picture of the boundary of a polygon, and for coloring the interior of such a polygon. These algorithms take O(v + p + q) time, where v is the number of polygon vertices, p is the polygon perimeter, and q is a resolution parameter. When the resolution q is fixed, these algorithms are asymptotically optimal
keywords	GIS, mapping, CAD, layout, pattern recognition, polyhedra, quadtree, planning, image processing, computer graphics
series	CADline
last changed	2003/06/02 13:58

_id	224b
authors	Preparata, Franco P.
year	1979
title	A Note on Locating a Set of Points in a Planar Subdivision
source	SIAM Journal of Computing. Society for Industrial and Applied Mathematics, November, 1979. vol. 8: pp. 542-545 : ill. includes some bibliographical references
summary	In this note the author shows algorithmically that a set of k points can be located in the planar subdivision induced by straight-line planar graph with n vertices in time O(k log k) + O(n) + O(k log n), given a preprocessing time O(n log n)
keywords	algorithms, computational geometry, point inclusion
series	CADline
last changed	2003/06/02 10:24

No more hits.