Applications of a semi-dynamic convex hull algorithm

作者: John Hershberger , Subhash Suri

DOI: 10.1007/3-540-52846-6_106

关键词:

摘要: We obtain new results for manipulating and searching semi-dynamic planar convex hulls (subject to deletions only), apply them derive improved bounds three problems in geometry scheduling. The hull are logarithmic time set splitting finding a tangent when the two not linearly separated. then these solve following problems: (1) [matching] given n red points blue plane, find matching of (by line segments) which no edges cross, (2) [scheduling] jobs with due dates, linear penalties late completion, single machine on process them, schedule that minimizes maximum penalty, (3) [covering] plane real numbers r1 r2, determine if one can cover all disks radii r2. Our O(n log n) O(n2 problem (3), an improvement by factor over previous bounds.

参考文章(16)
Dorit S. Hochbaum, Ron Shamir, An O( n log 2 n ) algorithm for the maximum weighted tardiness problem Information Processing Letters. ,vol. 31, pp. 215- 219 ,(1989) , 10.1016/0020-0190(89)90126-9
John Hershberger, Subhash Suri, Finding tailored partitions Journal of Algorithms. ,vol. 12, pp. 431- 463 ,(1991) , 10.1016/0196-6774(91)90013-O
David G. Kirkpatrick, Raimund Seidel, The ultimate planar convex hull algorithm SIAM Journal on Computing. ,vol. 15, pp. 287- 299 ,(1986) , 10.1137/0215021
Malcolm C. Fields, Greg N. Frederickson, A faster algorithm for the maximum weighted tardiness problem Information Processing Letters. ,vol. 36, pp. 39- 44 ,(1990) , 10.1016/0020-0190(90)90184-Y
F. P. Preparata, An optimal real-time algorithm for planar convex hulls Communications of the ACM. ,vol. 22, pp. 402- 405 ,(1979) , 10.1145/359131.359132
Herbert Edelsbrunner, Algorithms in Combinatorial Geometry ,(1987)
R.L. Graham, An efficient algorith for determining the convex hull of a finite planar set Information Processing Letters. ,vol. 1, pp. 132- 133 ,(1972) , 10.1016/0020-0190(72)90045-2
J. AKIYAMA, N. ALON, Disjoint simplices and geometric hypergraphs Annals of the New York Academy of Sciences. ,vol. 555, pp. 1- 3 ,(1989) , 10.1111/J.1749-6632.1989.TB22429.X
Mikhail J. Atallah, A matching problem in the plane Journal of Computer and System Sciences. ,vol. 31, pp. 63- 70 ,(1985) , 10.1016/0022-0000(85)90065-0
On the convex layers of a planar set IEEE Transactions on Information Theory. ,vol. 31, pp. 509- 517 ,(1985) , 10.1109/TIT.1985.1057060