2.7 - Finding the MIN/MAX slope (of lines connecting points in 2D) and its Counting Version
Algorithms by Sharma Thankachan
0:00 / 0:00
2.7 - Finding the MIN/MAX slope (of lines connecting points in 2D) and its Counting Version
1 750 просмотров · 6 л. назад
Algorithms by Sharma Thankachan
1,38 тыс. подписчиков
1 750 просмотров · 6 л. назад
Given a set of n points in 2D, we need to compute: (i) the pair of points such that the slope of the line segment connecting them is the MAXIMUM, (ii) the pair of points such that the slope of the line segment connecting them is the MINIMUM, and (iii) count the number of pairs such that the slope of the line segment connecting them is within a given range. All three problems can be solved in O(n log n) time. Part (iii) is based on a cleaver reduction to the inversion counting problem.