Talk:UVa 270

From Algorithmist
Jump to navigation Jump to search

Why is the initial sort by y increasing step needed? Because it lets you throw out points later? --Rrenaud 18:32, 19 Jan 2005 (EST)

It's an optimization that lets you do this: One may ask why the points whose indices are less than pivot point are omitted during each pivot turn. Those points can be safely ignored without worrying the final result won't be optimal. When an earlier point is a part of the optimal line, then the optimal result should have already been computed in an earlier pivot turn (remember the fact that the points were initially sorted based on their Cartesian coordinates).

Basically, it gives it another ordering, which in effect, lets you know, given two points, if we checked the line that the two points made already.

It's an optimization, that's all. You can emulate this by keeping a N^2 array, of course. Larry 18:40, 19 Jan 2005 (EST)

To be honest, I'm confused on how to sort all the points (with respect to pivot) if I don't omit the points below the pivot, and then suddenly I got the idea of sorting the points first based on coordinates. That's why I didn't include the sorting in the Optimization section. turuthok 3:48, 21 Jan 2005 (EST)

Sort by slope, special case verticals. Then each slope is just a rational number, which can be easily compared against each other. Then you can find colinear points because they will have the same slope. --Rrenaud 15:23, 21 Jan 2005 (EST)