
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Adaptive Algorithms for Planar Convex Hull Problems
HeeKap AHN Yoshio OKAMOTO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E94D
No.2
pp.182189 Publication Date: 2011/02/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E94.D.182
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science  Mathematical Foundations and Applications of Algorithms and Computer Science ) Category: Keyword: adaptive algorithms, convex hulls, computational geometry,
Full Text: PDF(261.5KB)>>
Summary:
We study problems in computational geometry from the viewpoint of adaptive algorithms. Adaptive algorithms have been extensively studied for the sorting problem, and in this paper we generalize the framework to geometric problems. To this end, we think of geometric problems as permutation (or rearrangement) problems of arrays, and define the "presortedness" as a distance from the input array to the desired output array. We call an algorithm adaptive if it runs faster when a given input array is closer to the desired output, and furthermore it does not make use of any information of the presortedness. As a case study, we look into the planar convex hull problem for which we discover two natural formulations as permutation problems. An interesting phenomenon that we prove is that for one formulation the problem can be solved adaptively, but for the other formulation no adaptive algorithm can be better than an optimal outputsensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a kdtree.

