作者: 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.