Jarvis March

Definition

Jarvis March is a computational algorithm used to find the convex hull of a set of points in the plane. This algorithm constructs the convex hull by identifying the outermost points that form a polygon enclosing all other points, making it an essential method in computational geometry for problems involving shape and boundary detection.

5 Must Know Facts For Your Next Test

1. The Jarvis March algorithm, also known as the gift-wrapping algorithm, works by starting from a leftmost point and wrapping around the other points to find the hull.
2. This algorithm is particularly intuitive as it mimics the action of wrapping a gift, which is where its alternate name comes from.
3. Its worst-case time complexity is O(nh), where n is the number of points and h is the number of points on the convex hull, making it inefficient for large sets with many points.
4. Jarvis March can handle both convex and non-convex sets of points, but it specifically focuses on producing the outer boundary.
5. The algorithm can be less efficient than others like Graham's Scan when dealing with large datasets, as it may require examining every point multiple times.

Review Questions

• How does the Jarvis March algorithm construct the convex hull and what is its initial step?
  • The Jarvis March algorithm starts by selecting the leftmost point from the set of points as the starting point for constructing the convex hull. It then repeatedly finds the next point that creates the smallest angle with the line formed by the last two points on the hull. This process continues until it wraps around back to the starting point, effectively creating a polygon that encompasses all other points in the set.
• Compare and contrast Jarvis March with Graham's Scan in terms of efficiency and approach to finding the convex hull.
  • Jarvis March has a time complexity of O(nh), which can be less efficient than Graham's Scan, which operates in O(n log n) due to its sorting step. While Jarvis March works in an intuitive manner by wrapping around points, Graham's Scan first sorts all points by polar angle relative to a reference point before constructing the hull using a stack. This makes Graham's Scan generally more efficient for larger datasets compared to Jarvis March.
• Evaluate the implications of using Jarvis March for real-world applications in computational geometry, considering its strengths and weaknesses.
  • Using Jarvis March for real-world applications can be beneficial due to its straightforward and intuitive approach, especially in scenarios with a small number of points or when visual clarity is required. However, its inefficiency in handling larger datasets poses challenges for applications needing rapid processing times, such as geographic information systems or robotics. As such, while Jarvis March provides valuable insight into basic geometric principles, other algorithms like Graham's Scan or QuickHull may be preferred in high-performance scenarios.

Related terms

Convex Hull: The smallest convex polygon that can enclose a set of points in a plane.

Graham's Scan: Another algorithm for finding the convex hull of a set of points that sorts the points by angle and then constructs the hull using a stack.

Gift Wrapping Algorithm: An algorithm similar to Jarvis March that iteratively selects the next point on the convex hull by 'wrapping' around the set of points.