Dynamically maintaining the widest k-dense corridor
In this paper, we propose an improved algorithm for dynamically maintaining the widest k-dense corridor as proposed in Shin et al. (Inform, Process. Lett. 68 (1998) 25-31). Our algorithm maintains a data structure of size O(n(2)), where n is the number of points present on the floor at the current instant of time. For each insertion/deletion of points, the data structure can be updated in O(nlogn) time, and the widest k-dense corridor in the updated environment can be reported in O(kn + nlogn) time. Another interesting variation of this problem, called query problem, is also considered in this paper, where the objective is to report the widest k-dense corridor containing a given query point q. We propose two schemes for answering this query. In the first scheme, an O(n(2)) space data structure can answer this query in O(nk) time. In the second scheme, we construct an O(nk) space data structure afresh for each query, and then answer the query in O(nklog([n/k])) time. (C) 2001 Elsevier Science B.V. All rights reserved.
corridors geometric duality levels of arrangement