Abstract
We study a geometric facility location problem under imprecision. Given n unit intervals in the real line, each with one of k colors, the goal is to place one point in each interval such that the resulting minimum color-spanning interval is as large as possible. A minimum color-spanning interval is an interval of minimum size that contains at least one point from a given interval of each color. We prove that if the input intervals are pairwise disjoint, the problem can be solved in O(n) time, even for intervals of arbitrary length. For overlapping intervals, the problem becomes much more difficult. Nevertheless, we show that it can be solved in \(O(n^2 \log n)\) time when \(k=2\), by exploiting several structural properties of candidate solutions, combined with a number of advanced algorithmic techniques. Interestingly, this shows a sharp contrast with the 2-dimensional version of the problem, recently shown to be NP-hard.
A. Acharyya was supported by the DST-SERB grant number SRG/2022/002277. V. Keikha was supported by the CAS PPPLZ grant L100302301, and the institutional support RVO: 67985807. M. Saumell was supported by the Czech Science Foundation, grant number 23-04949X. R. Silveira was partially supported by grant PID2019-104129GB-I00/MCIN/AEI/10.13039/501100011033.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abellanas, M., et al.: Smallest color-spanning objects. In: auf der Heide, F.M. (ed.) ESA 2001. LNCS, vol. 2161, pp. 278–289. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44676-1_23
Acharyya, A., Jallu, R.K., Keikha, V., Löffler, M., Saumell, M.: Minimum color spanning circle of imprecise points. Theor. Comput. Sci. 930, 116–127 (2022)
de Berg, M. (ed.): Ray shooting into a fixed direction. In: Ray Shooting, Depth Orders and Hidden Surface Removal. LNCS, vol. 703, pp. 67–84. Springer, Heidelberg (1993). https://doi.org/10.1007/BFb0029819
Chen, D.Z., Misiołek, E.: Algorithms for interval structures with applications. Theor. Comput. Sci. 508, 41–53 (2013)
Das, S., Goswami, P.P., Nandy, S.C.: Smallest color-spanning object revisited. Int. J. Comput. Geom. Appl. 19(5), 457–478 (2009)
Fiala, J., Kratochvíl, J., Proskurowski, A.: Systems of distant representatives. Discret. Appl. Math. 145(2), 306–316 (2005)
Fleischer, R., Xu, X.: Computing minimum diameter color spanning sets is hard. Inf. Process. Lett. 111(21–22), 1054–1056 (2011)
Hu, R., Zhang, J.: Computing k-centers of uncertain points on a real line. Oper. Res. Lett. 50(3), 310–314 (2022)
Li, S., Wang, H.: Dispersing points on intervals. Discret. Appl. Math. 239, 106–118 (2018)
Löffler, M., van Kreveld, M.: Largest and smallest convex hulls for imprecise points. Algorithmica 56(2), 235–269 (2010)
Löffler, M., van Kreveld, M.: Largest bounding box, smallest diameter, and related problems on imprecise points. Comput. Geom. 43(4), 419–433 (2010)
Naredla, A.M.: Algorithms for Geometric Facility Location: Centers in a Polygon and Dispersion on a Line. Ph.D. thesis, University of Waterloo (2023)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Acharyya, A., Keikha, V., Saumell, M., Silveira, R.I. (2024). Computing Largest Minimum Color-Spanning Intervals of Imprecise Points. In: Soto, J.A., Wiese, A. (eds) LATIN 2024: Theoretical Informatics. LATIN 2024. Lecture Notes in Computer Science, vol 14578. Springer, Cham. https://doi.org/10.1007/978-3-031-55598-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-55598-5_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-55597-8
Online ISBN: 978-3-031-55598-5
eBook Packages: Computer ScienceComputer Science (R0)