Quote:
Can anyone teach me what approach will be best and most effective in terms of time complexity?
The approach is brut force, test very single segment against every horizontal segment.
Apply the KISS method a list of N-1 segments, a list of Q horizontal segments, nothing fancy.
Complexity is (N-1)*Q
Quote:
I thought kd tree may help.
To use a method with this or with that, you need to have an idea of how it will help before.
When you search the correct algorithm to solve a problem:
- first choose brute force and evaluate the workload.
- Search an improves method and evaluate new workload, keep if workload reduction.
- try to improve further with another method or refinement.