Dynamically maintaining the widest \(k\)-dense corridor (Q5941092)

In this paper, we propose an improved algorithm for dynamically maintaining the widest \(k\)-dense corridor as proposed in \textit{C. S. Shin, S. Y. Shin} and \textit{K. Y. Chwa} [Inform. Process. Lett. 68, No. 1, 25-31 (1998; Zbl 0925.68433)]. 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(n\log n)\) time, and the widest \(k\)-dense corridor in the updated environment can be reported in \(O(kn+n\log n)\) 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(nk\log(\lfloor n/k\rfloor))\) time.