Route Curve Simplification Function

Problem

Design a function that simplifies a polyline representing a route. The input is a sequence of 2D coordinate points, and the goal is to produce a new sequence with fewer points while keeping the overall shape and important features of the original path intact. The simplification must respect a given maximum error threshold.

Function Signature

def simplify_route(points: List[Tuple[float, float]], epsilon: float) -> List[Tuple[float, float]]:
    pass

Example

Input:
points = [(0, 0), (1, 0.1), (2, -0.1), (3, 5), (4, 6), (5, 7), (6, 8.1), (7, 9), (8, 9.2), (9, 9.5)]
epsilon = 1.0

Output:
[(0, 0), (2, -0.1), (3, 5), (9, 9.5)]

Explanation: The algorithm removes points whose perpendicular distance from the line segment connecting the retained endpoints is less than or equal to epsilon. Points like (1, 0.1), (7, 9), and (8, 9.2) fall within the 1.0-unit error corridor and are discarded, while points marking significant deviations, such as (2, -0.1) and (3, 5), are kept.

Constraints

• The input list contains at least 2 points.
• Coordinates are floating-point values.
• epsilon is a non-negative float.
• The function should return a list of points in the same order as they appear in the input.

Follow-up

Provide test cases that cover typical scenarios, including a straight line, a path with a sharp corner, and a dense curve.