Paper: Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms

Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms

Frank Nielsen

Abstract:
In this paper, we review and analyze the complexity of a paradigm called grouping-and-querying which has been used in the past for computing convex hulls of points or objects on the plane, maximal and convex layer decompositions, lower envelopes of functions, etc. Then, we present new results concerning the computation of: (i) a transversal set for various families of geometric objects, (ii) a few (not necessarily connected) cells of a Voronoi diagram: Let S be a set of n points of the Euclidean plane E², we give an O(n log h) time algorithm for computing the Voronoi cells of the sites S'⊆ S, where h is the output-size. We extend this approach to higher dimensions.

Download the PS paper here © Springer-Verlag LNCS (328 KB, 8 pages, 2 figures).

The original publication is available at SpringerLink.

Bibtex entry:


@InProceedings{n-gqpgosa-2000,
	editor    = {Jin Akiyama and Mikio Kano and Masatsugu Urabe},
	title = {Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms},
	author= {Frank Nielsen},
	booktitle     = {Discrete and Computational Geometry, Japanese Conference, JCDCG'98,
               Tokyo, Japan, December 9-12, 1998, Revised Papers},
	publisher = {Springer},
	series    = {Lecture Notes in Computer Science},
	volume    = {1763},
	page = {250-257}
	year      = {2000},
	isbn      = {3-540-67181-1}
}

Publication:

Frank Nielsen,
Grouping and Querying: A Paradigm to Get Output-Sensitive Algorithms
Japan Conference on Discrete and Computational Geometry (JCDCG),
Lecture Notes in Computer Science (LNCS) Springer-Verlag,
Volume 1763, pp. 250-257, 2000.

Last updated, 2003.