You signed in with another tab or window.Reload to refresh your session.You signed out in another tab or window.Reload to refresh your session.You switched accounts on another tab or window.Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/algebra/sieve-of-eratosthenes.md
+3-1Lines changed: 3 additions & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -19,7 +19,9 @@ And we continue this procedure until we have processed all numbers in the row.
19
19
20
20
In the following image you can see a visualization of the algorithm for computing all prime numbers in the range $[1; 16]$. It can be seen, that quite often we mark numbers as composite multiple times.
21
21
22
-
<center></center>
22
+
<divstyle="text-align:center;">
23
+
<imgsrc="sieve_eratosthenes.png"alt="Sieve of Eratosthenes">
24
+
</div>
23
25
24
26
The idea behind is this:
25
27
A number is prime, if none of the smaller prime numbers divides it.
Copy file name to clipboardExpand all lines: src/geometry/basic-geometry.md
+12-4Lines changed: 12 additions & 4 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -112,7 +112,9 @@ The dot (or scalar) product $\mathbf a \cdot \mathbf b$ for vectors $\mathbf a$
112
112
Geometrically it is product of the length of the first vector by the length of the projection of the second vector onto the first one.
113
113
As you may see from the image below this projection is nothing but $|\mathbf a| \cos \theta$ where $\theta$ is the angle between $\mathbf a$ and $\mathbf b$. Thus $\mathbf a\cdot \mathbf b = |\mathbf a| \cos \theta \cdot |\mathbf b|$.
@@ -181,7 +183,9 @@ To see the next important property we should take a look at the set of points $\
181
183
You can see that this set of points is exactly the set of points for which the projection onto $\mathbf a$ is the point $C \cdot \dfrac{\mathbf a}{|\mathbf a|}$ and they form a hyperplane orthogonal to $\mathbf a$.
182
184
You can see the vector $\mathbf a$ alongside with several such vectors having same dot product with it in 2D on the picture below:
183
185
184
-
<center></center>
186
+
<divstyle="text-align:center;">
187
+
<imgsrc="https://i.imgur.com/eyO7St4.png"alt="Vectors having same dot product with a">
188
+
</div>
185
189
186
190
In 2D these vectors will form a line, in 3D they will form a plane.
187
191
Note that this result allows us to define a line in 2D as $\mathbf r\cdot \mathbf n=C$ or $(\mathbf r - \mathbf r_0)\cdot \mathbf n=0$ where $\mathbf n$ is vector orthogonal to the line and $\mathbf r_0$ is any vector already present on the line and $C = \mathbf r_0\cdot \mathbf n$.
@@ -192,14 +196,18 @@ In the same manner a plane can be defined in 3D.
192
196
###Definition
193
197
194
198
Assume you have three vectors $\mathbf a$, $\mathbf b$ and $\mathbf c$ in 3D space joined in a parallelepiped as in the picture below:
From school we know that we should multiply the area of the base with the height, which is projection of $\mathbf a$ onto direction orthogonal to base.
199
205
That means that if we define $\mathbf b \times \mathbf c$ as the vector which is orthogonal to both $\mathbf b$ and $\mathbf c$ and which length is equal to the area of the parallelogram formed by $\mathbf b$ and $\mathbf c$ then $|\mathbf a\cdot (\mathbf b\times\mathbf c)|$ will be equal to the volume of the parallelepiped.
200
206
For integrity we will say that $\mathbf b\times \mathbf c$ will be always directed in such way that the rotation from the vector $\mathbf b$ to the vector $\mathbf c$ from the point of $\mathbf b\times \mathbf c$ is always counter-clockwise (see the picture below).
This defines the cross (or vector) product $\mathbf b\times \mathbf c$ of the vectors $\mathbf b$ and $\mathbf c$ and the triple product $\mathbf a\cdot(\mathbf b\times \mathbf c)$ of the vectors $\mathbf a$, $\mathbf b$ and $\mathbf c$.
Copy file name to clipboardExpand all lines: src/geometry/convex_hull_trick.md
+6-2Lines changed: 6 additions & 2 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -17,7 +17,9 @@ The idea of this approach is to maintain a lower convex hull of linear functions
17
17
Actually it would be a bit more convenient to consider them not as linear functions, but as points $(k;b)$ on the plane such that we will have to find the point which has the least dot product with a given point $(x;1)$, that is, for this point $kx+b$ is minimized which is the same as initial problem.
18
18
Such minimum will necessarily be on lower convex envelope of these points as can be seen below:
One has to keep points on the convex hull and normal vectors of the hull's edges.
23
25
When you have a $(x;1)$ query you'll have to find the normal vector closest to it in terms of angles between them, then the optimum linear function will correspond to one of its endpoints.
@@ -90,7 +92,9 @@ Assume we're in some vertex corresponding to half-segment $[l,r)$ and the functi
90
92
91
93
Here is the illustration of what is going on in the vertex when we add new function:
92
94
93
-
<center></center>
95
+
<div style="text-align: center;">
96
+
<img src="li_chao_vertex.png" alt="Li Chao Tree vertex">
97
+
</div>
94
98
95
99
Let's go to implementation now. Once again we will use complex numbers to keep linear functions.
Copy file name to clipboardExpand all lines: src/geometry/intersecting_segments.md
+9-3Lines changed: 9 additions & 3 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -16,18 +16,24 @@ The naive solution algorithm is to iterate over all pairs of segments in $O(n^2)
16
16
Let's draw a vertical line $x = -\infty$ mentally and start moving this line to the right.
17
17
In the course of its movement, this line will meet with segments, and at each time a segment intersect with our line it intersects in exactly one point (we will assume that there are no vertical segments).
18
18
19
-
<center></center>
19
+
<divstyle="text-align:center;">
20
+
<imgsrc="sweep_line_1.png"alt="sweep line and line segment intersection">
21
+
</div>
20
22
21
23
Thus, for each segment, at some point in time, its point will appear on the sweep line, then with the movement of the line, this point will move, and finally, at some point, the segment will disappear from the line.
22
24
23
25
We are interested in the**relative order of the segments** along the vertical.
24
26
Namely, we will store a list of segments crossing the sweep line at a given time, where the segments will be sorted by their $y$-coordinate on the sweep line.
25
27
26
-
<center></center>
28
+
<divstyle="text-align:center;">
29
+
<imgsrc="sweep_line_2.png"alt="relative order of the segments across sweep line">
30
+
</div>
27
31
28
32
This order is interesting because intersecting segments will have the same $y$-coordinate at least at one time:
29
33
30
-
<center></center>
34
+
<divstyle="text-align:center;">
35
+
<imgsrc="sweep_line_3.png"alt="intersection point having same y-coordinate">
Copy file name to clipboardExpand all lines: src/geometry/lattice-points.md
+6-2Lines changed: 6 additions & 2 deletions
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -38,7 +38,9 @@ We have two cases:
38
38
This amount is the same as the number of points such that $0 < y \leq (k - \lfloor k \rfloor) \cdot x + (b - \lfloor b \rfloor)$.
39
39
So we reduced our problem to $k'= k - \lfloor k \rfloor$, $b' = b - \lfloor b \rfloor$ and both $k'$ and $b'$ less than $1$ now.
40
40
Here is a picture, we just summed up blue points and subtracted the blue linear function from the black one to reduce problem to smaller values for $k$ and $b$:
41
-
<center></center>
41
+
<divstyle="text-align:center;">
42
+
<imgsrc="lattice.png"alt="Subtracting floored linear function">
43
+
</div>
42
44
43
45
- $k < 1$ and $b < 1$.
44
46
@@ -51,7 +53,9 @@ We have two cases:
51
53
52
54
which returns us back to the case $k>1$.
53
55
You can see new reference point $O'$ and axes $X'$ and $Y'$ in the picture below:
54
-
<center></center>
56
+
<divstyle="text-align:center;">
57
+
<imgsrc="mirror.png"alt="New reference and axes">
58
+
</div>
55
59
As you see, in new reference system linear function will have coefficient $\tfrac 1 k$ and its zero will be in the point $\lfloor k\cdot n + b \rfloor-(k\cdot n+b)$ which makes formula above correct.
Defined this way, the distance corresponds to the so-called[Manhattan (taxicab) geometry](https://en.wikipedia.org/wiki/Taxicab_geometry), in which the points are considered intersections in a well designed city, like Manhattan, where you can only move on the streets horizontally or vertically, as shown in the image below:
Copy file name to clipboardExpand all lines: src/geometry/minkowski.md
+3-1Lines changed: 3 additions & 1 deletion
Display the source diff
Display the rich diff
Original file line number
Diff line number
Diff line change
@@ -41,7 +41,9 @@ We repeat the following steps while $i < |P|$ or $j < |Q|$.
41
41
42
42
Here is a nice visualization, which may help you understand what is going on.
43
43
44
-
<center></center>
44
+
<divstyle="text-align:center;">
45
+
<imgsrc="minkowski.gif"alt="Visual">
46
+
</div>
45
47
46
48
##Distance between two polygons
47
49
One of the most common applications of Minkowski sum is computing the distance between two convex polygons (or simply checking whether they intersect).