Dynamically maintaining the widest \(k\)-dense corridor (Q5941092)
From MaRDI portal
scientific article; zbMATH DE number 1635257
Language | Label | Description | Also known as |
---|---|---|---|
English | Dynamically maintaining the widest \(k\)-dense corridor |
scientific article; zbMATH DE number 1635257 |
Statements
Dynamically maintaining the widest \(k\)-dense corridor (English)
0 references
20 August 2001
0 references
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.
0 references
geometric duality
0 references
levels of arrangement
0 references
corridors
0 references