Closest approach of line segments

  • Context: Undergrad 
  • Thread starter Thread starter Lindley
  • Start date Start date
  • Tags Tags
    Approach Line
Click For Summary
SUMMARY

The discussion focuses on optimizing the process of finding all segments in set B that approach within a specified threshold distance of each segment in set A. While a naive O(n^2) approach is straightforward, the user suggests leveraging data structures like KD-trees for potential efficiency improvements, similar to point-based searches. However, the challenge lies in the fact that segments may approach or intersect without their endpoints being close, prompting consideration of alternative methods such as plane-sweep algorithms for better performance.

PREREQUISITES
  • Understanding of computational geometry concepts
  • Familiarity with KD-trees and their construction
  • Knowledge of plane-sweep algorithms
  • Basic principles of line segment intersection
NEXT STEPS
  • Research the implementation of KD-trees for line segment proximity queries
  • Study plane-sweep algorithms and their applications in computational geometry
  • Explore advanced data structures for spatial partitioning
  • Investigate algorithms for detecting line segment intersections
USEFUL FOR

Computer scientists, software engineers, and researchers in computational geometry looking to optimize algorithms for proximity queries among line segments.

Lindley
Messages
6
Reaction score
0
I have two sets of line segments, A and B. My goal is, for each segment in A, I want to find all segments in B which approach within some threshold distance.

Clearly this can be done in O(n^2) easily enough, but I think it's possible to do better. For instance, if I were working with points instead of lines, I could construct a KD-tree and do the lookup that way in O(n log n).

At first I was thinking perhaps I could construct 2 KD-trees, one for each end point, and do something with that. But it's possible one segment could approach or even intersect another without their endpoints being anywhere nearby, so that won't work. Now I'm trying to think if there's some way to do it with a plane-sweep algorithm.

Any ideas?
 
Physics news on Phys.org
There's not a computer science forum here? Wow, no there isn't. That sucks. Algorithms don't really belong to topology or geometry.
 
As a computational geometry problem, I figured this was close enough.
 

Similar threads

Undergrad Chiral symmetries in E[SUP]^n[/SUP]
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Find the closest distance between two lines segments?
  • · Replies 1 ·
Replies
1
Views
2K
Intersection of two line segments from uniform distribution
  • · Replies 17 ·
Replies
17
Views
3K
Graduate Working out a point / segment on a sphere
  • · Replies 3 ·
Replies
3
Views
2K
High School Calculating 'Typical' Grade of a Hiking Trail
  • · Replies 5 ·
Replies
5
Views
4K
Undergrad A set of numbers as a smooth curved changing manifold.
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Connecting N points pairwise in volume V, average density of lines?
  • · Replies 2 ·
Replies
2
Views
4K
Graduate Ordering Line Segments to form a 2D Polygon after slicing a 3D Tri Map
  • · Replies 1 ·
Replies
1
Views
3K
Translating reciprocating motion into a 45 degree rotation
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Help with a 3D Line Integral Problem (segmented line)
  • · Replies 14 ·
Replies
14
Views
2K