20 lines
1.0 KiB
Markdown
20 lines
1.0 KiB
Markdown
|
# HW6
|
|||
|
|
## Problem 1
|
|||
|
|
- 1.
|
|||
|
|
- 
|
|||
|
|
- 1. $N_{Del(n)}=3n-6$
|
|||
|
|
- 2. $v_{Del(n)}=n-1$
|
|||
|
|
- 3. $N_{Del(n)}=4n-6$
|
|||
|
|
- 4. $v_{Del(n)}=n$
|
|||
|
|
- 2. 
|
|||
|
|
Algorithm: First find the Voronoi diagram in O(nlogn), then for each intersection (both between edges and borders， including corners), find its distance to the point in the cell right next to it in O(n), and the one with the maximized distance is the P*
|
|||
|
|
Based on Triangle inequality, any point that is not on the intersection must have less distance to the nearest point compare to the intersection point right next to it on the same edge, thus we can find P* in O(nlogn)
|
|||
|
|
## Problem 2
|
|||
|
|
- 1.
|
|||
|
|
- 1. 
|
|||
|
|
- 2. 
|
|||
|
|
- 3. 
|
|||
|
|
(5, 6), (7, 10), (4, 7), (8, 9), (7, 9), (3, 5), (2, 8), (3, 10), (1, 4)
|
|||
|
|
- 4. 
|
|||
|
|
$1, 4, 7, 9, 8, 2, 8, 9, 7, 10, 3, 5, 6, 5, 3, 10, 7, 4, 1 \rArr 1, 4, 7, 9, 8, 2, 10, 3, 5, 6, 1$
|
|||
|
|
- 2. 
|