Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Một số biến thể của bài toán hình tròn tối tiểu bị ràng buộc
Tóm tắt
Cho một tập P gồm n điểm và một đường thẳng L, chúng tôi nghiên cứu ba biến thể quan trọng của bài toán hình tròn bao bọc tối thiểu như sau: Chúng tôi đề xuất ba thuật toán cho Bài toán (i). Thuật toán đầu tiên có thời gian chạy là O(nklogn) và không gian O(n). Thuật toán thứ hai hiệu quả trong trường hợp k≪n; nó có thời gian chạy là O(nlogn+nk+k²log³n) và không gian O(nlogn). Thuật toán thứ ba dựa trên tìm kiếm tham số và có thời gian chạy là O(nlogn+klog⁴n). Đối với Bài toán (ii), độ phức tạp về thời gian và không gian của thuật toán đề xuất lần lượt là O(nk) và O(n). Đối với Bài toán (iii), thuật toán đề xuất của chúng tôi có thời gian chạy O(nlogn) và không gian O(n).
Từ khóa
#hình tròn bao bọc tối thiểu #bài toán hình tròn tối thiểu #thuật toán #độ phức tạp thời gian #độ phức tạp không gianTài liệu tham khảo
Abellanas M, Hurtado F, Icking C, Klein R, Langetepe E, Ma L, Sacriston V (2001) The farthest color Voronoi diagram and related problems. In: 17th European workshop on computational geometry
Agarwal PK, Sharir M, Welzl E (1997) The discrete 2-center problem. In: 13th annual symposium on computational geometry, pp 147–155
Alt H, Arkin EM, Bronnimann H, Erickson J, Fekete SP, Knauer C, Lenchner J, Mitchell JSB, Whittlesey K (2006) Minimum-cost coverage of point sets by disks. In: Proc 22nd annual ACM symposium on computational geometry, pp 449–458
Bose P, Wang Q (2002) Facility location constrained to a polygonal domain. In: 5th Latin American symposium on theoretical informatics. LNCS, vol 2286, pp 153–164
Brass P, Knauer C, Na H-S, Shin C-S, Vigneron A (2009) Computing k-centers on a line. Technical report CoRR abs/0902.3282
Chan TM (1999) More planar two-center algorithms. Comput Geom 13:189–198
Cole R (1987) Slowing down sorting networks to obtain faster sorting algorithms. J ACM 34:200–208
Cole R, Salowe J, Steiger W, Szemeredi E (1989) An optimal-time algorithm for slope selection. SIAM J Comput 18:792–810
Gupta UI, Lee DT, Leung JY-T (1982) Efficient algorithms for interval graphs and circular-arc graphs. Networks 12:459–467
Hochbaum DS, Shmoys D (1985) A best possible heuristic for the k-center problem. Math Oper Res 10:180–184
Hurtado F, Sacristan V, Toussaint G (2000) Facility location problems with constraints. Stud Locat Anal 15:17–35
Hwang RZ, Chang RC, Lee RCT (1993) The searching over separators strategy to solve some NP-hard problems in subexponential time. Algorithmica 9:398–423
Karmakar A, Roy S, Das S (2008) Fast computation of smallest enclosing circle with center on a query line segment. Inf Process Lett 108:343–346
Kim SK, Shin CS (2000) Efficient algorithms for two-center problems for a convex polygon. In: Proc 6th international conference on computing and combinatorics. LNCS, vol 1858, pp 299–309
Lev-Tov N, Peleg D (2005) Polynomial time approximation schemes for base station coverage with minimum total radii. Comput Netw 47(4):489–501
Marchetti-Spaccamela A (1981) The p-center problem in the plane is NP-complete. In: Proc 19th Allerton conf on communication, control and computing, pp 31–40
Matousek J (1991) Randomized optimal algorithm for slope selection. Inf Process Lett 39:183–187
Megiddo N (1983) Linear-time algorithms for linear programming in R 3 and related problems. SIAM J Comput 12:759–776
Pahlavan K, Levesque AH (2005) Wireless information networks, vol 1, 2nd edn. Wiley, New York
Plesnik J (1987) A heuristic for the p-center problem in graphs. Discrete Appl Math 17:263–268
Roy S, Karmakar A, Das S, Nandy SC (2006) Constrained minimum enclosing circle with center on a query line segment MFCS, pp 765–776
Roy S, Bardhan D, Das S (2008) Base station placement on boundary of a convex polygon. J Parallel Distrib Comput 68:265–273
Vahrenhold J (2007) Line-segment intersection made in-place. Comput Geom 38:213–230
van Oostrum R, Veltkamp RC (2002) Parametric search made practical. In: SoCG: 18th symposium on computational geometry, pp 1–9