Voronoi Diagrams

nn points p1,,pnp_1,\cdots,p_n.

Nearest neighbor problem

举一个具象化的例子:

nn post offices

Find the closest post office

For which region, point pip_i is the closest point?

What is the region that pip_i servies?

(对于二维空间使用欧几里得距离定义的距离)两个最近点对连线线段的中垂线就是分界。

Definition of Voronoi Diagrams

A set PP of nn points p1,,pnp_1,\cdots,p_n

decomposition of R2\mathbb R^2 into regions R1,,RnR_1,\cdots,R_n.

for any qRiq\in R_i, pip_i is the closest point

Theorems

Cells of the Voronoi diagram of PP are convex.

Proof:

Consider pip_i. Draw the bisector of pipj,ji\overline{p_ip_j},j\neq i and let hjh_j be the half space the contains the side of the bisector that includes pip_i. The cell of pip_i is the intersection of all hjh_j’s.

If not all points of PP lie on a line, the Voronoi diagram is made of straight line segments or rays and it is connected.

  • the cells are convex regions from the previous proof
  • the finite cells are polygons
  • if there is a full line ll, then it implies that no bisector intersects ll, which means all points lie on a line.

The size of a planar Voronoi diagram is linear.

Proof:

mm: number of edges in Voronoi graph, II: number of vertices in Voronoi graph, HH: size infinite cell

Euler’s Formula: VE+R=2V-E+R=2

For infinite edges:

  • put a bounding box,加入边界盒后的点数为 VV,边数为 EE,面数为 RR.
  • R=n+1R=n+1 one for each input point + outside
  • all vertices have degree three, except four special corner vertices
  • 2E=3(V4)+4×22E=3(V-4)+4\times 2
  • E=4+H+m,V=4+H+IE=4+H+m,V=4+H+I

一顿推导,得出:

I=2n2H2n5I=2n-2-H\le2n-5

m=3nH33n6m=3n-H-3\le3n-6

Computing 2D Voronoi Diagrams

idea: sweep line

problem: the next point, can totally change everything above the sweep line.

we cannot assume we have compute the diagram above the sweep line correctly.

idea: define a region above the sweep line that we know is stable. Anything in this region is closer to pp than any point below the line i.e. cell of cc above the curve is stable.

sweep line: Y=lY=l

curve: Pi(l)=(Xai)2+(Ybi)2=(Yl)2P_i(l)=(X-a_i)^2+(Y-b_i)^2=(Y-l)^2

Initially, all the Y-coordinates are the event points.

挨着向下扫描,在扫描线上方的点,两两之间用中垂线 bisector 分隔开,扫描线上方的点和扫描线用抛物线分隔开。这样得到的区域就是稳定的。

Other event points are when parabola segment disappear.

Can be found by checking three adjacent parabola segments.

We need a data structure for inserting and deleting parabola segments i.e., a balanced BST.

O(nlogn)O(n\log n) running time:

logn\log n pere event points

O(n)O(n) events points (since size of the diagram is linear)

Generalization of Voronoi Diagrams

farthest point Voronoi diagram

higher order nearest neighbor

kk-order: same set of kk nearest neighbors

different distance measure L,L1L_\infty,L_1\cdots

segments, curves etc.

distance based on shape enlarging

Triangulations

Let PP be set of nn points in R2\mathbb R^2

Theorem: Any trangulation of PP has 2n2k2n-2-k triangles and 3n3k3n-3-k edges.

kk is number of edges on Convex Hull of PP.

edge e=pqe=\overline{pq} is illegal if minα<minβ\min\alpha\lt\min\beta.

Observation: Let ee be an illegaal edge of T\mathcal T, let T\mathcal T' be triangulation obtained from T\mathcal T by flipping ee, then A(T)>A(T)A(\mathcal T')\gt A(\mathcal T)

Pseudo code for legal triangulation:

  1. while T\mathcal T contains illegal edge e=pqe=\overline{pq}

    let rr and ss be the other points in the triangles incident to ee

    remove ee and add st\overline{st}

  2. return T\mathcal T

The Delaunay Triangulation

Let PP be set of nn points in R2\mathbb R^2, let V(P)\mathcal V(P) be the Voronoi diagram of PP.

Let D(P)\mathcal D(P) be the dual graph of V(P)\mathcal V(P), D(P)\mathcal D(P) is the Delaunay graph of PP. 沃诺依图的对偶图是德劳内三角剖分

Theorem: D(P)\mathcal D(P) is a plane graph

Assume that PP is in geneal position: no four points cocircular, not three points colinear.

Theorem:

  1. p,q,rPp,q,r\in P are vertices of the same face of D(P)\mathcal D(P)\Lrarr circle through p,q,rp,q,r contains no other point of PP in its interior.
  2. p,qPp,q\in P from an edge of D(P)\mathcal D(P)\Lrarr there is a closed disk CC that contains pp and qq on its boundary and doesn’t contain any other point of PP

Computing Delaunay Triangulation

using randomized incremental construction

as with point location, we maintain T\mathcal T and a point location data structure D\mathcal D.

3D Convex Hull

convex hull ofo nn points in 3D3D

composed of

  • vertices
  • edges
  • faces

Complexity of a 3D CH is linear

  1. 假设边是“线”: 在计算几何的上下文中,这里的“线”指的是 3D 凸包的边。 这些边形成凸包的边界。
  2. 从放置在凸包顶点顶部的光源投射边缘的阴影: 想象一下,您有一个光源直接位于凸包最高点(顶点)上方。 现在,将每条边的阴影投影到凸包下方的平坦表面上。 这类似于物体在光照射下投射的阴影。
  3. 由于凸性,边缘的阴影不会交叉: 因为根据定义,凸包是凸形状,因此当投影到平面上时,其边缘的阴影不会相交或相互交叉。 该特性是船体凸度的直接结果。
  4. 由于我们是从不在凸包外部的点进行投影: 投影是从凸包内部的点(具体来说,在最高顶点的顶部)完成的。 这确保了阴影投射在凸包内而不是外部。

Gift Wrapping for 3DCH

wrap a plane around the convex hull

  1. project the points to 2D, find the 2D CH
  2. an edge of 2D CH is a starting point
  3. perform a DFS on the faces. (the face is marked so we don’t visit it again)

O(nh)O(nh) time, nn is number of points, hh is output size.

Randomized Incremental Algorithm for 3DCH

  1. randomly shuffle the points
  2. create the convex hull of the first four points
  3. for i=1,,ni=1,\cdots,n insert pip_i

adding pip_i:

  1. faces visible from pip_i should be removed
  2. new faces should be added, touching the boundary of the formerly visible faces

an edges is a boundary edge if out of two faces next to it one is visible but the other is not.

to find the visible faces

  • for every point pp maintain a list of faces l(p)l(p) visible from pp
  • for every face ff maintain a list of points l(f)l(f) visible from ff
  • for every face fl(p)f\in l(p) place a point and back to the pointer pl(f)p\in l(f).

the points that can see ff, l(f)l(f) is a subset of points that can see f1f_1 and f2f_2, l(f)l(f1)l(f2)l(f)\sub l(f_1)\cup l(f_2)

如果一个点能同时看到两个相邻的面,那么这个点一定在这两个面延长面共同的上方。

if FiF_i is the list of faces visible from pip_i then adding pip_i takes fFil(f)\sum_{f\in F_i}|l(f)| time asymptotically

i.e. O(ni)O(\frac{n}{i}) on average.

O(nlogn)O(n\log n) expected running time