Nearest point to set of line segments
I have a point p, and n line segments in the 2d space. Is there a way I can preprocess the line segments so that I can efficiently (i.e. sublineraly) find the line segment closest (i.e with lowest perpendicular distance) to P?
This is a real-world problem we're trying to solve. The best (approximate) answer we have is to preprocess the ends of the line segments of the points into a quad tree/2d kd tree, and find the nearest point. This should lead to a nearly optimal answer (or maybe even correct answer) in most cases.
Alternately one can use Mongodb's geonear, which works with points as well.
Can we do better than this, particularly in terms of accuracy?
If your segments are uniformly spread and not too long, you can think of a gridding approach: choose a cell size and determine for every cell which segment crosses it (this is done by "drawing" the segments on the grid). Then for a query point, find the nearest non-empty cell, by visiting neighborhoods of increasing size, and compute the exact nearest distance to the segment(s) so found. You need to continue the search as long as the distance between the query point and the next cells does not exceed the shortest distance found so far.
If the distribution is not uniform, a quad-tree decomposition can be better.
More generally, a suitable strategy is to use any acceleration device that quickly will report a small number of candidate segments, with a guaranty: the nearest segment must be among the candidates.
- Linked List Replacement Function with Head, Tail, and Size Management
- Efficient Array Storage for Binary Tree
- How to render data and initialize an UI event handling upon this data after the data has been loaded by an asynchronous API call?
- Hackerrank Repeated String infinite loop problem
- Using asterisk and spaces print the letter R [ 21*20]
- Split a collection into `n` parts with LINQ?
- How can I enhance the time complexity of arranging bricks into stacks based on specific conditions?
- JS - recursive function on multidimensional array to filter out only "checked" items (and its parents if a child is selected)
- Octree implementation in Rust: why is the insert function duplicating insertions and how could I go about fixing this?
- how to traverse an NxN grid diagonally
- Name of binary data structures that contain fixed-length components?
- Insert after specific element in LinkedList java
- inserting in binary tree doesn't work using java
- Generate simple URL patterns from a list of examples
- Explain time complexity of permutations using the mathematical expression
- Why AddAfter() has constant time?
- 2D peak finding algorithm in O(n) worst case time?
- C# Multiway Linked List
- Find Elements occurring odd number of times in a list
- Difference between back tracking and dynamic programming
- How to build a trie for finding exact phonetic matches, sorted globally by weight, and paginated? (Building off this example)
- Is there an algorithm to find the closest element to X in an unsorted array in Ω(logN)?
- Difference between vertices and edges [Graphs, Algorithm and DS]
- How to find the time comlexity when comparing sublists?
- My quicksort algorithm is very slow so what can I do to make it faster?
- How are Linked Lists implemented in the Ready Queue before moving onto the scheduler during the PCB implementation?
- Convert a sorted array into a height-balanced binary search tree by picking middle element -- why does it work?
- Minimum number of coins needed for amount with infinite coins available. Understanding the optimization
- How is my algorithm for stock span problem incorrect?
- Generic Key/Value pair collection in that preserves insertion order?