What is a line segment?

A line segment is the part of a line that is represented by a connection of two end points. It encompasses both ends of the line, as well as all points in between. The length of a line cannot be measured, but the length of a segment can be measured. If a line segment is bounded by two end points, it is called a closed line segment, whereas an open line segment does not have both endpoints. A line segment with a single endpoint is called half-open. A closed line segment contains every point on the line that exists between the two end points. For example, if L is a line, then AB is a line segment of line L where A and B are endpoints of the line segment.

The sides of geometrical shapes like triangles, squares are examples of line segments. The line segment is either an edge or a diagonal when both of its endpoints are vertices of a polyhedron, depending on whether they are adjacent vertices. A chord is also a line segment. The endpoints of the chord lie on itself.

Properties of Line Segment

• There are two ends on the line segment which denotes that the ends of the segement are fixed.
• Since, a line segment is bounded by two end points, the length of the line segment is fixed.
• A line segment is constructed by a set of points where the two end points define the starting and beginning of this set.

Point of Intersection

When two or more lines in a plane cross, they form intersecting lines. The lines cross each other at a specific point which is known as the point of intersection. In the figure below, two lines P and Q intersect each other and meet at point O, which is the point of intersection.

Any Pair Segments Problem

It is an important problem in computational geometry. The problem states that given n line segments, find whether there exists a pair of segments that intersect each other. The straight forward solution to this algorithm is to check each and every pair of line segments one by one to determine if any pair of segments intersect. Since, there are n line segments and checking for one pair takes constant time, the time complexity of the algorithm is O(n²). This method is not much efficient and a more time efficient algorithm is required.

Sweep Line Algorithm

The sweep algorithm is an efficient algorithm to find whether any pair of segments intersect from given n line segments. The algorithm begins by arranging the endpoints along the x-axis from left to right. It then uses a vertical line that passes through all the lines one by one from left to right. The vertical line first meets the left end of any particular line, sweeps through all its points, then meets the right end of that line. It maintains a list of active segments(segments whose left end is encountered but right end is not) to check if the segments intersect.

Consider that there n line segments with 2n end points(since each segment has 2 end points). The steps of the algorithm are described below in detail.

1.  Sort the x coordinates of the end points from left to right end. While sorting, keep a flag to signify whether the current point is the left end point or right end point of the line.
2. Start sweeping the vertical line from the left most point. For each point that intersects with the sweep line, do the following:
   1. If the point if the left end point of a line, add the corresponding line segment to the list of active segments. Check whether the line intersects with any of the active segments. If an intersection pair is found, compute the point of intersection and add the lines to the intersection list.
   2. If the point if the right end point of a line, remove the corresponding line segment from the list of active segments.

The algorithm uses a line that sweeps through each end point from left to right, therefore it is called sweep line algorithm. Many additional geometric algorithms, such as calculating the 2D Voronoi diagram, use the Sweep Line approach. The algorithm solves the problem in O(n log n) time. The most suitable data structure to implements the algorithm is self-balancing binary trees such as AVL tree. The heap data structure can be used to perform the sorting operation of the algorithm. The min-heap can be build in O(n) time and the minimum element can be in O(log n) time which makes it efficient to use.

Context and Applications

This topic is very useful for both undergraduate and postgraduate students. Especially for:

• Bachelors in Computer Science
• Masters in Computer Science
• Bachelor of Technology in Computer Science
• Masters of Computer Applications

Related Topics

• Convex hull
• Segment in Computer Graphics
• Segment Table in Computer Graphics
• Attributes of the segment table

Practice Problems

Q1. What is a line segment?

1. A section of line.
2. An area of line.
3. A division of line
4. All

Correct answer: 1. A section of line.

Explanation- A line segment is the part of a line. It is defined by two separate endpoints in geometry. A line segment, on the other hand, is a section of a line that links two points.

Q2: What is computational geometry?

1. It is the branch of mathematics in which we study about geometric problems.
2. It is the branch of computer science where we study about the algorithms for geometric problems.
3. None
4. Both

Correct answer: 2. It is the branch of computer science where we study algorithms for geometric problems.

Explanation- While the emphasis is on theory and algorithms, computational geometry does deal with geometric objects.

Q3: Which algorithm is used to find whether any pair of segments intersect from a given set of segments?

1. Sweep line algorithm
2. Floyed Warshell algorithm
3. Dijkstra algorithm
4. Kruskal's algorithm

Correct answer- 1. Sweep line algorithm

Explanation- The Sweep Line Algorithm is used to solve the problem to find the line segments which intersect from a given set of points. It takes in O (n log n) time, where n is the number of line segments provided to the algorithm. The method arranges the endpoints along the x-axis from the left end to the right end, then tests for intersections by passing a vertical line that meets all end points from the left end to the right end.

Q4- Which data structure is suitable to implement the Sweep line algorithm?

1. Binary tree
2. Linked list
3. AVL tree
4. Queue

Correct Answer- 3. AVL tree

Explanation- The algorithm is best implemented using a self-balancing tree. An AVL tree is also a self-balancing tree where the height of the left and right sub tree can differ by at most one node.

Q5- How many endpoints do a line segment has?

1. Two endpoints
2. Three endpoints
3. Four endpoints
4. Either two or three endpoints

Correct Answer- 1. Two endpoints

Explanation- A line segment is a part of a line bounded by two endpoints.