Dispersing and grouping points on planar segments. (English) Zbl 1514.68308
Summary: Motivated by (continuous) facility location, we study the problem of dispersing and grouping points on a set of segments (of streets) in the plane. In the former problem, given a set of \(n\) disjoint line segments in the plane, we investigate the problem of computing a point on each of the \(n\) segments such that the minimum Euclidean distance between any two of these points is maximized. We prove that this 2D dispersion problem is NP-hard, in fact, it is NP-hard even if all the segments are parallel and are of unit length. This is in contrast to the polynomial solvability of the corresponding 1D problem by S. Li and H. Wang [LIPIcs – Leibniz Int. Proc. Inform. 64, Article 52, 12 p. (2016; Zbl 1398.68620)], where the intervals are in 1D and are all disjoint. With this result, we also show that the Independent Set problem on Colored Linear Unit Disk Graph (meaning the convex hulls of points with the same color form disjoint line segments) remains NP-hard, and the parameterized version of it is in W[2]. In the latter problem, given a set of \(n\) disjoint line segments in the plane we study the problem of computing a point on each of the \(n\) segments such that the maximum Euclidean distance between any two of these points is minimized. We present a factor-1.1547 approximation algorithm which runs in \(O(n\log n)\) time. Our results can be generalized to the Manhattan distance.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q27 | Parameterized complexity, tractability and kernelization |
| 68W25 | Approximation algorithms |
| 90B85 | Continuous location |
Citations:
Zbl 1398.68620References:
| [1] | Aurenhammer, F.; Drysdale, R. L.S.; Kraser, H., Farthest line segment Voronoi diagrams, Inf. Process. Lett., 100, 220-225 (2006) · Zbl 1185.68769 |
| [2] | Baur, C.; Fekete, S., Approximation of geometric dispersion problems, (Proc. of APPROX’98 (1998)), 63-75 · Zbl 0908.68180 |
| [3] | de Berg, M.; Khosravi, A., Optimal binary space partition for segments in the plane, Int. J. Comput. Geom. Appl., 22, 3, 187-206 (2012) · Zbl 1267.68268 |
| [4] | Bereg, S.; Ma, F.; Wang, W.; Zhang, J.; Zhu, B., On some matching problems under the color-spanning model, Theor. Comput. Sci., 786, 26-31 (2019) · Zbl 1429.68318 |
| [5] | Breu, H., Algorithmic aspects of constrained unit disk graphs (1996), Department of Computer Science, UBC: Department of Computer Science, UBC Canada, PhD dissertation |
| [6] | Cevallos, A.; Eisenbrand, F.; Zenklusen, R., Local search for max-sum diversification, (Proc. of SODA’17 (2017)), 130-142 · Zbl 1410.68397 |
| [7] | Chandra, B.; Halldorsson, M., Approximation algorithms for dispersion problems, J. Algorithms, 38, 438-465 (2001) · Zbl 0974.68153 |
| [8] | Clark, B.; Colbourn, C.; Johnson, D., Unit disk graphs, Discrete Math., 86, 1-3, 165-177 (1990) · Zbl 0739.05079 |
| [9] | Fellows, M.; Hermelin, D.; Rosamond, F.; Vialette, S., On the parameterized complexity of multiple-interval graph problems, Theor. Comput. Sci., 410, 1, 53-61 (2009) · Zbl 1161.68038 |
| [10] | Hassin, R.; Rubinstein, S.; Tamir, A., Approximation algorithms for maximum dispersion, Oper. Res. Lett., 21, 133-137 (1997) · Zbl 0888.90144 |
| [11] | Hunt, H. B.; Marathe, M. V.; Radhakrishnan, V.; Ravi, S. S.; Rosenkrantz, D. J.; Stearns, R. E., NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, J. Algorithms, 26, 2, 238-274 (1998) · Zbl 0894.68105 |
| [12] | Li, S.; Wang, H., Dispersing points on intervals, (Proc. of ISAAC’16. Proc. of ISAAC’16, LIPIcs, vol. 64 (2016)), 52:1-52:12 · Zbl 1398.68620 |
| [13] | Li, S.; Wang, H., Dispersing points on intervals, Discrete Appl. Math., 239, 106-118 (2018) · Zbl 1410.68372 |
| [14] | Knuth, D. E.; Raghunathan, A., The problem of compatible representatives, SIAM J. Discrete Math., 5, 3, 422-427 (1992) · Zbl 0825.68494 |
| [15] | Marx, D., Efficient approximation schemes for geometric problems?, (Proc. 13th European Symposium on Algorithms (ESA’05) (2005)), 448-459 · Zbl 1162.68822 |
| [16] | Papadopoulou, E.; Dey, S. K., On the farthest line-segment Voronoi diagram, Int. J. Comput. Geom. Appl., 23, 6, 443-460 (2013) · Zbl 1317.68252 |
| [17] | Pruente, J., Minimum diameter color-spanning sets revisited, Discrete Optim., 34, Article 100550 pp. (2019) · Zbl 1506.90231 |
| [18] | Ravi, R.; Rosenkrantz, D.; Tayi, G., Heuristic and special case algorithms for dispersing problems, Oper. Res., 42, 299-310 (1994) · Zbl 0805.90074 |
| [19] | Sydow, M., Approximation guarantees for max sum and max min facility dispersion with parameterised triangle inequality and applications in result diversification, Math. Appl., 42, 241-257 (2014) · Zbl 1409.68335 |
| [20] | Wang, D. W.; Kuo, Y-S., A study on two geometric location problems, Inf. Process. Lett., 28, 281-286 (1988) · Zbl 0675.68071 |
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.
