In this paper we consider efficient algorithms in a semi-dynamic situation, that is, input data are entered one by one while some of them may be deleted on the way and then finally we are required to solve a given problem. We evaluate such algorithms by a three tuple (Ti, Td, Tp) where Ti and Td denote the time needed for insertion and deletion of data, respectively, and Tp is the time for solving a given problem. We present efficient algorithms for several different problems including the convex hull problem, the visible-pair enumeration problem and the visibility region problem.
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
Tetsuo ASANO, Elena LODI, "Solving Semi-Dynamic Geometric Problems" in IEICE TRANSACTIONS on transactions,
vol. E73-E, no. 2, pp. 265-269, February 1990, doi: .
Abstract: In this paper we consider efficient algorithms in a semi-dynamic situation, that is, input data are entered one by one while some of them may be deleted on the way and then finally we are required to solve a given problem. We evaluate such algorithms by a three tuple (Ti, Td, Tp) where Ti and Td denote the time needed for insertion and deletion of data, respectively, and Tp is the time for solving a given problem. We present efficient algorithms for several different problems including the convex hull problem, the visible-pair enumeration problem and the visibility region problem.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e73-e_2_265/_p
Copy
@ARTICLE{e73-e_2_265,
author={Tetsuo ASANO, Elena LODI, },
journal={IEICE TRANSACTIONS on transactions},
title={Solving Semi-Dynamic Geometric Problems},
year={1990},
volume={E73-E},
number={2},
pages={265-269},
abstract={In this paper we consider efficient algorithms in a semi-dynamic situation, that is, input data are entered one by one while some of them may be deleted on the way and then finally we are required to solve a given problem. We evaluate such algorithms by a three tuple (Ti, Td, Tp) where Ti and Td denote the time needed for insertion and deletion of data, respectively, and Tp is the time for solving a given problem. We present efficient algorithms for several different problems including the convex hull problem, the visible-pair enumeration problem and the visibility region problem.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Solving Semi-Dynamic Geometric Problems
T2 - IEICE TRANSACTIONS on transactions
SP - 265
EP - 269
AU - Tetsuo ASANO
AU - Elena LODI
PY - 1990
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E73-E
IS - 2
JA - IEICE TRANSACTIONS on transactions
Y1 - February 1990
AB - In this paper we consider efficient algorithms in a semi-dynamic situation, that is, input data are entered one by one while some of them may be deleted on the way and then finally we are required to solve a given problem. We evaluate such algorithms by a three tuple (Ti, Td, Tp) where Ti and Td denote the time needed for insertion and deletion of data, respectively, and Tp is the time for solving a given problem. We present efficient algorithms for several different problems including the convex hull problem, the visible-pair enumeration problem and the visibility region problem.
ER -