Skip to content

Commit cc1f087

Browse files
committed
improve format
1 parent 0999f66 commit cc1f087

File tree

1 file changed

+3
-4
lines changed

1 file changed

+3
-4
lines changed

src/geometry/nearest_points.md

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -173,12 +173,12 @@ An alternative method, originally proposed by Rabin in 1976, arises from a very
173173
</div>
174174

175175

176-
We will consider only the squares containing at least one point. Denote by $n_1, n_2, \dots, n_k$ the number of points in each of the $k$ remaining squares. Assuming at least two points are in the same or in adjacent squares, and that there are no duplicated points, the time complexity is $\Theta\left(\sum\limits_{i=1}^k n_i^2\right)$. We can look for duplicated points in expected linear time using a hash table, and in the affirmative case, the answer is this pair.
176+
We will consider only the squares containing at least one point. Denote by $n_1, n_2, \dots, n_k$ the number of points in each of the $k$ remaining squares. Assuming at least two points are in the same or in adjacent squares, and that there are no duplicated points, the time complexity is $\Theta\!\left(\sum\limits_{i=1}^k n_i^2\right)$. We can look for duplicated points in expected linear time using a hash table, and in the affirmative case, the answer is this pair.
177177

178178
??? info "Proof"
179179
For the $i$-th square containing $n_i$ points, the number of pairs inside is $\Theta(n_i^2)$. If the $i$-th square is adjacent to the $j$-th square, then we also perform $n_i n_j \le \max(n_i, n_j)^2 \le n_i^2 + n_j^2$ distance comparisons. Notice that each square has at most $8$ adjacent squares, so we can bound the sum of all comparisons by $\Theta(\sum_{i=1}^{k} n_i^2)$. $\quad \blacksquare$
180180

181-
Now we need to decide on how to set $d$ so that it minimizes $\Theta\left(\sum\limits_{i=1}^k n_i^2\right)$.
181+
Now we need to decide on how to set $d$ so that it minimizes $\Theta\!\left(\sum\limits_{i=1}^k n_i^2\right)$.
182182

183183
#### Choosing d
184184

@@ -246,8 +246,7 @@ ll dist2(pt a, pt b) {
246246
}
247247

248248

249-
// O(n)
250-
pair<int,int> closest_pair_of_points_rand_ints(vector<pt> P) {
249+
pair<int,int> closest_pair_of_points(vector<pt> P) {
251250
int n = int(P.size());
252251
assert(n >= 2);
253252

0 commit comments

Comments
 (0)