Smallest color-spanning object revisited. (English) Zbl 1178.65020
Summary: Given a set of \(n\) colored points in \(\mathbb R^{2}\) with a total of \(m (3 \leq m \leq n)\) colors, the problem of identifying the smallest color-spanning object of some predefined shape is studied. We consider two different shapes: (i) corridor and (ii) rectangle of arbitrary orientation. Our proposed algorithm for identifying the smallest color-spanning corridor is simple and runs in \(O(n ^{2} \log n)\) time using \(O(n)\) space. A dynamic version of the problem is also studied, where new points may be added, and the narrowest color-spanning corridor at any instance can be reported in \(O(mn(\alpha (n)) ^{2} \log m\)) time. Our algorithm for identifying the smallest color-spanning rectangle of arbitrary orientation runs in \(O(n ^{3} \log m\)) time and \(O(n)\) space.
MSC:
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
References:
| [1] | DOI: 10.1016/0167-8655(90)90080-L · Zbl 0941.68725 · doi:10.1016/0167-8655(90)90080-L |
| [2] | DOI: 10.1007/978-3-642-61568-9 · doi:10.1007/978-3-642-61568-9 |
| [3] | DOI: 10.1137/0215019 · Zbl 0613.68043 · doi:10.1137/0215019 |
| [4] | DOI: 10.1016/j.ipl.2005.02.013 · Zbl 1182.68331 · doi:10.1016/j.ipl.2005.02.013 |
| [5] | DOI: 10.1016/0020-0190(89)90136-1 · Zbl 0689.68058 · doi:10.1016/0020-0190(89)90136-1 |
| [6] | DOI: 10.1007/BF02189323 · Zbl 0770.68111 · doi:10.1007/BF02189323 |
| [7] | Janardan R., Nordic J. Comput. 1 pp 231– |
| [8] | DOI: 10.1016/S0304-3975(00)00370-4 · Zbl 0974.68218 · doi:10.1016/S0304-3975(00)00370-4 |
| [9] | DOI: 10.1007/BF02574706 · Zbl 0744.68132 · doi:10.1007/BF02574706 |
| [10] | Sharir M., Davenport-Schinzel Sequences and Their Geometric Applications (1995) · Zbl 0834.68113 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
