A combinatorial theorem on labeling squares with points and its application. (English) Zbl 1137.05050
Summary: We present a combinatorial theorem on labeling disjoint axis-parallel squares of edge length two using points. Given an arbitrary set of disjoint axis-parallel squares of edge length two, we show that if we label points on the boundary of all squares (one for each square) and define a distance label graph such that there is an edge between any two labeling points if and only if their \(L_\infty\)-distance is at most \(1-\varepsilon\) (\(0 < \varepsilon < 1\)), then the maximum connected component of the graph contains \(\Theta(1/\varepsilon)\) vertices, which is tight. With this theorem we present a new and simple factor-\((3 + \varepsilon)\) approximation for labeling points with axis-parallel squares under the slider model.
MSC:
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C90 | Applications of graph theory |
| 90C27 | Combinatorial optimization |
References:
| [1] | Agarwal P, Pach J (1995) Combinatorial geometry. John Wiley and Sons · Zbl 0881.52001 |
| [2] | Datta A, Lenhof II-P, Schwarz C, Smid M (1995) Static and dynamic algorithms for k-point clustering problems. J Algorithms 19:474–503 · Zbl 0836.68115 · doi:10.1006/jagm.1995.1048 |
| [3] | Doddi S, Marathe M, Mirzaian A, Moret B, Zhu B (1997) Map labeling and its generalizations. In Proc 8th ACM-SIAM Symp on Discrete Algorithms (SODA’97), New Orleans, LA, pp. 148–157 · Zbl 1321.68435 |
| [4] | Jiang M, Qian J, Qin ZP, Zhu B, Cimikowski R (2003) A simple factor-3 approximation for labeling points with circles. Inform Process Lett 87(2):101–105 · Zbl 1161.68878 · doi:10.1016/S0020-0190(03)00256-4 |
| [5] | van Kreveld M, Strijk T, Wolff A (1999) Point set labeling with sliding labels. Comp Geom Theory and Appl 13:21–47 · Zbl 0930.68153 |
| [6] | Lee DT, Wong CK (1980) Voronoi diagrams in L1(L metrics with 2-dimensional storage applications. SIAM J Comp 9:200–211 · Zbl 0447.68111 · doi:10.1137/0209017 |
| [7] | Preparata FP, Shamos MI (1985) Computational geometry: An introduction. Springer-Verlag · Zbl 0575.68059 |
| [8] | Qin ZP, Zhu B (2002) A factor-2 approximation for labeling points with maximum sliding labels. In Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT’02). Springer-Verlag, LNCS series vol. 2368, pp. 100–109 · Zbl 1078.68829 |
| [9] | Zhu B, Qin ZP (2002) New approximation algorithms for map labeling with sliding labels. J Combinatorial Optimization 6(1):99–110 · Zbl 1058.90080 · doi:10.1023/A:1013326409918 |
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.
