Closest approach of line segments

In summary, the conversation discusses the goal of finding all segments in set A that are within a certain distance of segments in set B. While this can be easily achieved in O(n^2), the speaker believes it can be done more efficiently. Suggestions are made, such as using KD-trees or implementing a plane-sweep algorithm. The conversation also mentions the lack of a computer science forum to discuss such problems.
  • #1
Lindley
7
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
  • #2
There's not a computer science forum here? Wow, no there isn't. That sucks. Algorithms don't really belong to topology or geometry.
 
  • #3
As a computational geometry problem, I figured this was close enough.
 

FAQ: Closest approach of line segments

What is the closest approach of two line segments?

The closest approach of two line segments is the shortest distance between the two segments. It can be measured by finding the closest points on each segment and calculating the distance between them.

How is the closest approach of line segments calculated?

The closest approach of line segments can be calculated using the vector projection method or the closest point on each segment method. Both methods involve finding the closest points on each segment and calculating the distance between them.

Can the closest approach of line segments be negative?

No, the closest approach of line segments cannot be negative. It is always a positive value representing the shortest distance between the two segments.

What does the closest approach of line segments tell us?

The closest approach of line segments gives us information about the proximity of two line segments. It can help us determine if the segments intersect or if one segment is within a certain distance of the other.

How is the closest approach of line segments used in real-world applications?

The closest approach of line segments is used in various fields such as computer graphics, robotics, and physics. It can be used to determine collision detection, proximity of objects, and path planning for robots.

Similar threads

B Calculating 'Typical' Grade of a Hiking Trail
Replies
5
Views
2K
Intersection of two line segments from uniform distribution
Replies
17
Views
2K
I A set of numbers as a smooth curved changing manifold.
Replies
3
Views
3K
I Find the closest distance between two lines segments?
Replies
1
Views
2K
Connecting N points pairwise in volume V, average density of lines?
Replies
2
Views
3K
Translating reciprocating motion into a 45 degree rotation
Replies
5
Views
2K
A How Does Non-Euclidean Geometry Differ from Euclid's Postulates?
Replies
3
Views
2K
Ordering Line Segments to form a 2D Polygon after slicing a 3D Tri Map
Replies
1
Views
3K
I Can the area be understood as the "number of points"?
Replies
27
Views
6K
B A Simpler Way to Find the Shaded Area?
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top