-
Notifications
You must be signed in to change notification settings - Fork 1
/
theory.html
349 lines (340 loc) · 20.4 KB
/
theory.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>VisualHull2D - Theory</title>
<link rel="stylesheet" type="text/css" href="style.css">
<script type="text/javascript" async
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/MathJax.js?config=TeX-MML-AM_CHTML">
</script>
<style>
body {
text-align: justify;
width: 80%;
}
</style>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-TEMocfGvRuD1rIAacqrknm5BQZ7W7uWitoih+jMNFXQIbNl16bO8OZmylH/Vi/Ei" crossorigin="anonymous">
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-jmxIlussZWB7qCuB+PgKG1uLjjxbVVIayPJwi6cG6Zb4YKq0JIw+OMnkkEC7kYCq" crossorigin="anonymous"></script>
<link rel="stylesheet" href="pseudocode.min.css">
<script src="pseudocode.min.js"></script>
</head>
<body>
<h1>Definition</h1>
Let \( X \) be a set of points in \( \mathbb{R}^{k} \).
The convex hull of \( X \) is the smallest convex set that contains all points in \( X \).<br/>
If \( X \) is finite, then the convex hull of \( X \) is a \( k \)-polytope. <br/>
In the finite, \( \mathbb{R}^{2} \) case, the convex hull of \( X \) is a convex polygon.<br/>
In the finite case, the convex hull of \( X \) can be also defined as the set of all the convex combinations
of the points of \( X \):
\[ \mathrm{ConvexHull}(X) = \left\{\left.\sum_{i=1}^{|X|} \alpha_i x_i \right| (\forall i:\ \alpha_i \ge 0) \wedge \sum_{i=1}^{|X|} \alpha_i = 1 \right\} \]
<h1>Applications</h1>
Finding the convex hull of a set of points is useful in all kinds of fields, most notably:
<ul>
<li>Physics Engines</li>
<li>Image Processing</li>
<li>Competitive Programming</li>
</ul>
Given that the amount of points of which we want to find the convex hull can be very large,
it is important not only that we have correct ways of finding it, but also that they're fast.<br/>
In this document the <a href="https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann%E2%80%93Landau_notations">Bachmann–Landau notation</a>
will be used to describe the computational complexity of the presented algorithms.
<h1>Algorithms</h1>
Optimal algorithms for finding the convex hull exist for the \( \mathbb{R}^{2} \) and \( \mathbb{R}^{3} \) cases.
In this context "optimal" means an algorithm that takes \( O(kn\log{h}) \) steps, where \( n := |X| \), \( h \) is
the number of vertices in the convex hull (it is determined after the algorithm has found the convex hull) and \( k \) is the number of dimensions.<br/>
Even if optimal algorithms exist, generally is enough to have an efficient algorithm, one that takes \( O(k^{d}n\log{n}) \) where \( d \) is some fixed number in \( \mathbb{R}_0^{+} \).<br/>
We will focus on the \( \mathbb{R}^{2} \) case, but some of the presented algorithms are trivally generalizable
to higher dimensions.
<h2>Naïve</h2>
Since \( X \) is finite, the convex set of \( X \) is a polygon. We want to find its edges; to do that, we
try all possible edges, and test whether all points lie exactly in one of the semi-planes defined by that
edge: if it's true, then that edge is part of the convex hull.
<pre id="naive-code" style="display: none;">
\begin{algorithmic}
\FUNCTION{Naïve}{$X$}
\STATE $n := |X|$
\STATE $S := \emptyset$
\FOR{$i := 1$ \TO $n$}
\FOR{$j := i + 1$ \TO $n$}
\STATE $L := \emptyset$
\STATE $U := \emptyset$
\STATE $p(x) := \mathrm{semiplane\ defined\ by\ the\ line\ from}\ X[i]\ \mathrm{to}\ X[j]$
\FORALL{$x \in X$}
\IF{$p(x) \le 0$}
\STATE $L \gets L \cup \{ x \}$
\ENDIF
\IF{$p(x) \ge 0$}
\STATE $U \gets U \cup \{ x \}$
\ENDIF
\ENDFOR
\IF{$|L| = n$ \OR $|U| = n$}
\STATE $S \gets S \cup \{ \langle X[i], X[j] \rangle \}$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $S$
\ENDFUNCTION
\end{algorithmic}
</pre>
<div id="naive"><br/></div><br/>
This algorithm takes \( \Theta(n^{3}) \) steps in the \( \mathbb{R}^{2} \) case.<br/>
It can be easily generalized to the \( \mathbb{R}^{k} \) case, taking \( \Theta(kn^{k + 1}) \) steps.<br/>
A smarter version of this algorithm breaks the innermost loop as soon as two points on opposing sides of the line are found.
<script>pseudocode.render(document.getElementById("naive-code").textContent, document.getElementById("naive"), {});</script>
<h2>Gift Wrapping</h2>
This algorithm was independently created by <a href="https://dl.acm.org/citation.cfm?id=321564">Chand & Kapur (1970)</a> and by <a href="https://www.sciencedirect.com/science/article/pii/0020019073900203">R. A. Jarvis (1973)</a>.<br/>
The algorithm starts by picking a point known to be on the convex hull: it can be the lowest, the highest, the rightmost or the leftmost.
Then it selects the next point such that all other points lie in the right semiplane defined by the line passing through those two points.
It then repeats the process starting from the last point until it reaches the starting point.
<pre id="gift-code" style="display: none;">
\begin{algorithmic}
\FUNCTION{GiftWrapping}{$X$}
\STATE $i := 1$
\STATE $P[i] := $ leftmost point in $X$
\STATE $K := $ null
\WHILE{$K \ne P[0]$}
\STATE $K \gets $ any point in $X$ that is not $P[i]$
\FORALL{$x \in X \setminus \{ P[i] \}$}
\STATE $p(x) := $ semiplane defined by the line from $P[i]$ to $K$
\IF{$p(x) > 0$}
\STATE $K \gets x$
\ENDIF
\ENDFOR
\STATE $i \gets i + 1$
\STATE $P[i] := K$
\ENDWHILE
\RETURN $P$
\ENDFUNCTION
\end{algorithmic}
</pre>
<div id="gift"><br/></div><br/>
This algorithm takes \( \Theta(nh) \) steps in the \( \mathbb{R}^{2} \) case.
<script>pseudocode.render(document.getElementById("gift-code").textContent, document.getElementById("gift"), {});</script>
<h2>QuickHull</h2>
This algorithm was independently created by <a href="https://dl.acm.org/citation.cfm?id=355766">W. Eddy (1977)</a> and by <a href="https://www.sciencedirect.com/science/article/pii/0020019078900212">A. Bykat (1978)</a>.<br/>
The algorithm works in two phases:
<ol>
<li>Splits the input in 2 sets separated by a line</li>
<li>Recursively excludes point from the convex hull</li>
</ol>
In the first phase the algorithm selects two points known to be in the convex hull (two of the lowest, the highest, the rightmost and the leftmost).
Then, it separates the points that lie on opposite sides of the line passing through the two previously selected points.
It then calls the second phase on those two sets.<br/>
In the second phase the algorithm takes a segment and some points all on one side of this line. It finds the furthest point
from the line, creates a triangle with that point and the given segment and categorize points: if a point is inside the triangle,
it gets discarded; the other points are grouped according to the side of the triangle they're on and the second phase it's
recursively called on those two groups of points.
If one side (excluding the given segment) has no points on it, it becomes part of the convex hull.
<pre id="quick-code" style="display: none;">
\begin{algorithmic}
\FUNCTION{QuickHull}{$X$}
\STATE $S := \emptyset$
\STATE $x_1 := $ leftmost point in $X$
\STATE $x_2 := $ rightmost point in $X$
\STATE $Q_1 := \emptyset$
\STATE $Q_2 := \emptyset$
\STATE $p(x) := $ semiplane defined by the line from $x_1$ to $x_2$
\FORALL{$x \in X \setminus \{ x_1, x_2 \}$}
\IF{$p(x) > 0$}
\STATE $Q_1 \gets Q_1 \cup \{ x \}$
\ELSE
\STATE $Q_2 \gets Q_2 \cup \{ x \}$
\ENDIF
\ENDFOR
\RETURN \CALL{FindHull}{$Q_1,\ x_1,\ x_2$} $\cup$ \CALL{FindHull}{$Q_2,\ x_1,\ x_2$}
\ENDFUNCTION
\FUNCTION{FindHull}{$Q,\ x_1,\ x_2$}
\IF{$|Q| = 0$}
\RETURN $\{ \langle x_1, x_2 \rangle \}$
\ENDIF
\STATE $D = $ some random point in $Q$
\FORALL{$x \in Q$}
\IF{dist($\overline{x_1 x_2}$, $x$) > dist($\overline{x_1 x_2}$, $D$)}
\STATE $D \gets x$
\ENDIF
\ENDFOR
\STATE $Q_1 := \emptyset$
\STATE $Q_2 := \emptyset$
\FORALL{$x \in Q$}
\IF{$x$ is inside triangle($x_1,\ D,\ x_2$)}
\STATE discard $x$
\ELSEIF{$x$ is outside the $\overline{x_1 D}$ edge}
\STATE $Q_1 \gets Q_1 \cup \{ x \}$
\ELSEIF{$x$ is outside the $\overline{x_2 D}$ edge}
\STATE $Q_2 \gets Q_2 \cup \{ x \}$
\ENDIF
\ENDFOR
\RETURN \CALL{FindHull}{$Q_1,\ x_1,\ D$} $\cup$ \CALL{FindHull}{$Q_2,\ x_2,\ D$}
\ENDFUNCTION
\end{algorithmic}
</pre>
<div id="quick"><br/></div><br/>
This algorithm takes \( O(n^{2}) \) steps in the \( \mathbb{R}^{2} \) case.<br/>
If we're lucky that the splits always divide the points in two almost equally sized sets, the algorithm takes \( \Omega(n \log{n}) \) steps.<br/>
It can be generalized for the \( \mathbb{R}^{k} \) case, taking \( O(k^{2} n^{2}) \) steps in the worst case and \( \Omega(k^{2} n \log{n}) \) steps if we're lucky.
<script>pseudocode.render(document.getElementById("quick-code").textContent, document.getElementById("quick"), {});</script>
<h2>Monotone Chain</h2>
This algorithm was created by <a href="https://www.sciencedirect.com/science/article/pii/0020019079900723">A. M. Andrew (1979)</a>.<br/>
The algorithm first sorts the points in lexicographic ascending order. Then it builds the lower and upper convex hulls
in the following way: starting from the first point (the last for the upper side) it continues to add points in order until
there is a right turn. When a right turn is detected, it removes the last point that is part of the convex hull until there
are only left turns.
<pre id="mono-code" style="display: none;">
\begin{algorithmic}
\FUNCTION{MonotoneChain}{$X$}
\STATE $Q := $ sorted($X$)
\STATE $U := $ list()
\STATE $L := $ list()
\FOR{$i := 1$ \TO $|Q|$}
\WHILE{$|L| \ge 2$ \AND $L[-2] \to L[-1] \to Q[i]$ is a right turn}
\STATE pop from $L$
\ENDWHILE
\STATE push $Q[i]$ into $L$
\ENDFOR
\FOR{$i := |Q|$ \TO $1$}
\WHILE{$|U| \ge 2$ \AND $U[-2] \to U[-1] \to Q[i]$ is a right turn}
\STATE pop from $U$
\ENDWHILE
\STATE push $Q[i]$ into $U$
\ENDFOR
\STATE pop from $L$
\STATE pop from $U$
\RETURN concat($L$, $U$)
\ENDFUNCTION
\end{algorithmic}
</pre>
<div id="mono"><br/></div><br/>
This algorithm takes \( O(n \log{n}) \) steps in the \( \mathbb{R}^{2} \) case.<br/>
The number of steps is dominated by the sort operation, which takes \( O(n \log{n}) \) steps,
while the remaining part of the algorithm takes \( \Theta(n) \) steps.
<script>pseudocode.render(document.getElementById("mono-code").textContent, document.getElementById("mono"), {});</script>
<h2>Kirkpatrick-Seidel</h2>
This algorithm was created by <a href="https://hdl.handle.net/1813/6417">David G. Kirkpatrick and Raimund Seidel (1983)</a>.<br/>
The algorithm should do something like the following:
First find a vertical line that divides the given
point set in two approximately equal sized parts. Next determine the "bridge" crossing
this line, i.e. the edge of the upper hull that intersects this line. Eliminate the points
that lie underneath the bridge, and finally apply the algorithm recursively to the two
sets of the remaining points on the left and right side of the vertical line.
The only difficult part in such an algorithm appears to be the construction of the
bridge.
Finding the bridge in linear time: We are given a set S of n points in the plane and a vertical
line L which has points of S to its left and right. We are to find the edge of the upper
hull of S that intersects L. If two edges intersect L, i.e. L contains a vertex v of the
upper hull, we want to identify the edge for which v is the left endpoint. Call this
edge the bridge and its endpoints bridge points. Let us define a supporting
line of S to be a nonvertical straight line which contains at least one point of S but
has no points of S above it. Obviously the bridge must be contained in some supporting
line. Call this line b and let Sb be the slope of b.
For our purposes, finding the bridge means identifying the two bridge points. One
possible way of achieving this is to successively eliminate points from S as candidates
for bridge points. For this purpose we pair up the points of S into In |S|/2 couples.
The following two lemmas show how forming pairs of points facilitates the elimination of
candidates for bridge points.
LEMMA 3.1. Let p, q be a pair ofpoints of S. If x(p)=x(q) and y(p) > y(q) then q cannot be a bridge point.
Proof. Trivial.
LEMMA 3.2. Let p, q be a pair of points of S with x(p) < x(q), and let Spq be the
slope of the straight line h through p and q.
(1) If Spq > Sb then p cannot be a bridge point.
(2) If Spq < Sb then q cannot be a bridge point.
Proof (for case (1); the proof for case (2) is symmetrical). Assume p was a bridge
point. By virtue of Spq > Sb and x(p) < x(q), q would lie above the bridge line b which
would contradict the fact that b is a supporting line of S.
Q.E.D.
Proof. Trivial.
To test whether Spq > Sb it suffices to find the supporting line h of S with
slope Spq and to determine whether h contains points of S to the right or to the left
of L. Of course, finding this supporting line h requires linear time which is clearly too
expensive to be done for every one of the n/2 pairs individually. However, this
problem can be overcome by judiciously choosing a slope Sh with the property that if
Sh > Sb then Spq > Sh (and hence Spq > Sb) for a large number of pairs p, q and, if Sh < Sb
then Spq < Sh (and hence Spq < Sb) for a large number of pairs p, q. A natural choice for
an Sh with this property is the median of the slopes of the lines defined by the n/2
pairs of points.
<pre id="kirk-seidel-code" style="display: none;">
\begin{algorithmic}
\FUNCTION{UpperHull}{$X$}
\STATE $x_1 := $ leftmost point in $X$
\STATE $x_2 := $ rightmost point in $X$
\IF{ $x_1 = x_2$ }
\STATE print $x_1$ and stop
\ENDIF
\STATE remove the points that have the same x as $x_1$ and $x_2$ except these 2
\RETURN \CALL{Connect}{$x_1,\ x_2,\ X$}
\ENDFUNCTION
\FUNCTION{Connect}{$x_1,\ x_2,\ X$}
\STATE $a :=$ median of x-es in $X$
\STATE $(i,j) :=$ \CALL{Bridge}{$X,\ a$}
\STATE $X_l :=$ points to the left of bridge
\STATE $X_r :=$ points to the right of bridge
\IF{ $i = x_1$ }
\STATE print $x_1$
\ELSE
\STATE\CALL{Connect}{$x_1,\ i,\ X_l$}
\ENDIF
\IF{ $j = x_2$ }
\STATE print $x_2$
\ELSE
\STATE\CALL{Connect}{$j,\ x_2,\ X_r$}
\ENDIF
\ENDFUNCTION
\FUNCTION{Bridge}{$X,\ a$}
\STATE $CANDIDATES := \emptyset$
\IF{ $|X| = 2$ }
\STATE\RETURN $(i,j)$
\ENDIF
\STATE Make $N/2$ ordered pairs of points, if you can't pair a point put it into $CANDIDATES$, call these $PAIRS$
\STATE If some pair in $PAIRS$ has the same x, put the upper one in $CANDIDATES$ and throw away the pair
\STATE let $k(p_i,p_j)$ be the slope from point $p_i$ to $p_j$
\STATE call $K$ the median of $k$ for points in $PAIRS$
\STATE Let MAX be the set of points in $X$, st y(p)-K*x(p) is maximum.
\STATE Let $p_k$ be the point in $MAX$ with minimum x-coordinate.
\STATE Let $p_m$ be the point in $MAX$ with maximum x-coordinate.
Let p,, be the point in MAX with maximum x-coordinate.
\IF{ x($p_k$) ≤ a \AND x($p_m$) > a }
\STATE return((k, m)).
\ELSEIF{x($p_m$) < a}
\STATE for all $PAIRS$ insert $p_j$ in $CANDIDATES$
\STATE for all $PAIRS$ with slope less than $K$, insert $p_i$ in $CANDIDATES$
\ELSEIF{X(pk) > a }
\STATE for all $PAIRS$ insert $p_i$ in $CANDIDATES$
\STATE for all $PAIRS$ with slope greater than $K$, insert $p_i$ in $CANDIDATES$
\ENDIF
\RETURN \CALL{Bridge}{$CANDIDATES,\ A$}
\ENDFUNCTION
\end{algorithmic}
</pre>
<div id="kirk-seidel"><br/></div><br/>
This algorithm takes \( O(n \log{h}) \) steps in the \( \mathbb{R}^{2} \) case.<br/>
The algorithm needs a linear time median algorithm in two places,
however you can take an element at random instead of the median and it becomes a randomized algorithm with the same expected complexity.
<script>pseudocode.render(document.getElementById("kirk-seidel-code").textContent, document.getElementById("kirk-seidel"), {});</script>
<h2>Graham Scan</h2>
This algorithm was created by <a href="https://www.sciencedirect.com/science/article/pii/0020019072900452">Ronald Graham (1972)</a>.<br/>
The algorithm first chooses a point which is known to be part of the convex hull (eg. the leftmost point).
Then the points are sorted by angle with this point. It then builds the convex hull in the following way:
starting from the first point it continues to add points in order until there is a right turn.
When a right turn is detected, it removes the last point that is part of the convex hull until there are only left turns.
<pre id="graham-code" style="display: none;">
\begin{algorithmic}
\FUNCTION{GrahamScan}{$X$}
\STATE $x_1 := $ leftmost point in $X$
\STATE $Q := $ sorted($X\setminus \{ x_1 \}$)
\STATE $H := $ list($x_1$)
\FOR{$i := 1$ \TO $|Q|$}
\WHILE{$|H| \ge 2$ \AND $H[-2] \to H[-1] \to Q[i]$ is a right turn}
\STATE pop from $H$
\ENDWHILE
\STATE push $Q[i]$ into $H$
\ENDFOR
\RETURN $H$
\ENDFUNCTION
\end{algorithmic}
</pre>
<div id="graham"><br/></div><br/>
This algorithm takes \( O(n \log{n}) \) steps in the \( \mathbb{R}^{2} \) case.<br/>
The number of steps is dominated by the sort operation, which takes \( O(n \log{n}) \) steps,
while the remaining part of the algorithm takes \( \Theta(n) \) steps.
<script>pseudocode.render(document.getElementById("graham-code").textContent, document.getElementById("graham"), {});</script>
</body>
</html>