Red-Blue Intersection Reporting for Objects of Non-Constant Size.

Autor:	Bozanis, P., Kitsios, N., Makris, C., Tsakalidis, A.
Předmět:	COMPUTER input-output equipment ALGORITHMS COMPUTATIONAL geometry GEOMETRIC series RECURSIVE functions RECURSION theory
Zdroj:	Computer Journal; 1996, Vol. 39 Issue 6, p541-546, 6p
Abstrakt:	Let Q1 be a set of ‘red’ geometric objects and Q2 a set of ‘blue’ ones. The objects in Q1 and Q2 are of arbitrarily large description size but each one is the union of simpler constant size components. We consider the problem of reporting all intersections between objects of Q1 and objects of Q2 in a time that depends on the size of the output. This is equivalent to painting the constant size objects in Q1 and Q2 and reporting colour intersections between Q1 and Q2. We present a technique that yields simple output-sensitive algorithms for many kinds of geometric objects. We also show that, using the same technique, it is possible to report all intersecting pairs in a set of objects in an output-sensitive manner. [ABSTRACT FROM AUTHOR]
Databáze:	Complementary Index
Externí odkaz:	Zobrazit plný text záznamu