The search functionality is under construction.

The search functionality is under construction.

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 output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a *k*d-tree.

- Publication
- IEICE TRANSACTIONS on Information Vol.E94-D No.2 pp.182-189

- Publication Date
- 2011/02/01

- Publicized

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.E94.D.182

- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hee-Kap AHN, Yoshio OKAMOTO, "Adaptive Algorithms for Planar Convex Hull Problems" in IEICE TRANSACTIONS on Information,
vol. E94-D, no. 2, pp. 182-189, February 2011, doi: 10.1587/transinf.E94.D.182.

Abstract: 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 output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a *k*d-tree.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E94.D.182/_p

Copy

@ARTICLE{e94-d_2_182,

author={Hee-Kap AHN, Yoshio OKAMOTO, },

journal={IEICE TRANSACTIONS on Information},

title={Adaptive Algorithms for Planar Convex Hull Problems},

year={2011},

volume={E94-D},

number={2},

pages={182-189},

abstract={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 output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a *k*d-tree.},

keywords={},

doi={10.1587/transinf.E94.D.182},

ISSN={1745-1361},

month={February},}

Copy

TY - JOUR

TI - Adaptive Algorithms for Planar Convex Hull Problems

T2 - IEICE TRANSACTIONS on Information

SP - 182

EP - 189

AU - Hee-Kap AHN

AU - Yoshio OKAMOTO

PY - 2011

DO - 10.1587/transinf.E94.D.182

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E94-D

IS - 2

JA - IEICE TRANSACTIONS on Information

Y1 - February 2011

AB - 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 output-sensitive algorithm for the planar convex hull problem. To further pursue the possibility of adaptive computational geometry, we also consider constructing a *k*d-tree.

ER -