Abstract: 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.
Publication Year: 1979
Publication Date: 1979-04-01
Language: en
Type: article
Indexed In: ['crossref', 'pubmed']
Access and Citation
Cited By Count: 404
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot