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. L ett. 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 i nstant of time. For each insertion/deletion of points, the data structure c an be updated in O(nlogn) time, and the widest k-dense corridor in the upda ted 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 contai ning 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 quer y in O(nk) time. In the second scheme, we construct an O(nk) space data str ucture afresh for each query, and then answer the query in O(nklog([n/k])) time. (C) 2001 Elsevier Science B.V. All rights reserved.