Happy Ending Convex n-gon Problem

from manim import * class HappyEndingProblem(Scene): def construct(self): # Title setup title = Tex("Happy Ending Problem").scale(1.5) subtitle = Tex("The Erdős–Szekeres Theorem").scale(0.8) subtitle.next_to(title, DOWN) self.play(Write(title), Write(subtitle)) self.wait(2) self.play(FadeOut(title), FadeOut(subtitle))

def show_convex_hull_evolution(self, n_points): # Create random points (in general position) points = self.generate_general_position_points(n_points) # Plot points dots = VGroup(*[Dot(point) for point in points]) labels = VGroup(*[ Text(f"{i+1}", font_size=24).next_to(dot, UP) for i, dot in enumerate(dots) ]) self.play(Create(dots), Create(labels)) # Show convex hull at different stages for k in range(3, min(n_points, 6) + 1): convex_hull = self.get_convex_hull(points[:k]) hull_polygon = Polygon(*points[:k], color=BLUE, fill_opacity=0.3) self.play( Create(hull_polygon), *[Indicate(dots[i]) for i in range(k)] ) # Label the convex hull hull_label = Tex(f"{k}-gon", color=BLUE).next_to(hull_polygon, UP) self.play(Write(hull_label)) self.wait(1) # Fade out for next iteration self.play( FadeOut(hull_polygon), FadeOut(hull_label) )

def generate_general_position_points(self, n): """Generate points in general position (no three collinear)""" points = [] while len(points) < n: new_point = np.round(np.random.uniform(-4, 4, 2), 1) valid = True # Check for collinearity for i in range(len(points)): for j in range(i+1, len(points)): for k in range(j+1, len(points)): if self.are_collinear(points[i], points[j], points[k]): valid = False break if valid: points.append(new_point) return points def are_collinear(self, a, b, c): """Check if three points are collinear""" return abs((b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])) < 1e-6 def get_convex_hull(self, points): """Compute convex hull using Andrew's monotone chain algorithm""" if len(points) <= 1: return points # Sort points lexographically points = sorted(points, key=lambda x: [x[0], x[1]]) # Build lower hull lower = [] for p in points: while len(lower) >= 2 and self.cross(lower[-2], lower[-1], p) <= 0: lower.pop() lower.append(p) # Build upper hull upper = [] for p in reversed(points): while len(upper) >= 2 and self.cross(upper[-2], upper[-1], p) <= 0: upper.pop() upper.append(p) return lower[:-1] + upper[:-1] def cross(self, o, a, b): return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

from manim import * import numpy as np class HappyEndingProblem(Scene): def construct(self): # Title scene self.show_title() # Explanation of the problem self.show_problem_explanation() # Case study with 5 points self.show_case_study_n5() # General theorem explanation self.show_general_theorem() # Conclusion self.show_conclusion() def show_title(self): title = Tex("Happy Ending Problem").scale(1.5) subtitle = Tex("The Erdős–Szekeres Theorem").scale(0.9) subtitle.next_to(title, DOWN) self.play( Write(title), FadeIn(subtitle, shift=UP) ) self.wait(2) self.play( FadeOut(title, shift=UP), FadeOut(subtitle, shift=DOWN) ) def show_problem_explanation(self): # Problem statement problem = Text("For any n ≥ 3, find the smallest N(n) such that").scale(0.8) continuation = Text("any N(n) points in general position contain").scale(0.8) conclusion = Text("a convex n-gon.").scale(0.8) continuation.next_to(problem, DOWN, aligned_edge=LEFT) conclusion.next_to(continuation, DOWN, aligned_edge=LEFT) group = VGroup(problem, continuation, conclusion).center() # Show problem statement self.play(Write(group)) self.wait(3) # Show minimal cases minimal = Tex("N(3)=3,\\ N(4)=5,\\ N(5)=9,\\ \\dots").scale(1.2) minimal.next_to(group, DOWN, buff=1) self.play(FadeIn(minimal, shift=UP)) self.wait(2) # Clear the scene self.play(*[FadeOut(mob) for mob in self.mobjects]) def show_case_study_n5(self): # Create 9 points in general position points = self.generate_general_position_points(9) dots = VGroup(*[Dot(point) for point in points]) # Show all points self.play(Create(dots)) self.wait() # Animate through subsets sequences = [ [0, 1, 2, 3, 6], # Shows a quad + point without forming 5-gon [0, 1, 2, 3, 4], # Forms convex 5-gon [0, 2, 4, 6, 8] # Another convex 5-gon ] for seq in sequences: selected_points = [points[i] for i in seq] # Highlight selected points animations = [] for i in seq: animations.append(dots[i].animate.set_color(YELLOW)) self.play(*animations) self.wait(0.5) # Show convex hull polygon = Polygon(*selected_points, color=BLUE, fill_opacity=0.3) label = Tex("5-gon", color=BLUE).next_to(polygon, UP) self.play(Create(polygon), Write(label)) self.wait(2) # Clean up for next iteration self.play( Uncreate(polygon), FadeOut(label), *[dots[i].animate.set_color(WHITE) for i in seq] ) # Clear for next section self.play(FadeOut(dots)) def show_general_theorem(self): # Theorem statement theorem = Tex( "\\text{For any integer } n \\geq 3,\\text{ there exists a smallest}\\\\" + "N(n)\\text{ such that any } N(n)\\text{ points in general position}\\\\" + "\\text{contain a convex } n\\text{-gon.}", tex_to_color_map={"N(n)": BLUE, "n": YELLOW} ).scale(0.9) bound = Tex( "N(n) \\leq \\binom{2n-5}{n-3} + 1 \\approx 4^{n}", tex_to_color_map={"N(n)": BLUE} ).next_to(theorem, DOWN) self.play(Write(theorem)) self.wait(3) # Show bound self.play(Write(bound)) self.wait(3) # Show known values known = VGroup( Tex("N(3) = 3"), Tex("N(4) = 5"), Tex("N(5) = 9"), Tex("N(6) = 17") ).arrange(RIGHT, buff=1).next_to(bound, DOWN, buff=1) self.play(LaggedStart(*[Write(k) for k in known], lag_ratio=0.5)) self.wait(2) # Clear for conclusion self.play(*[FadeOut(mob) for mob in self.mobjects]) def show_conclusion(self): # Happy ending story story = Text("The problem is named after its happy ending:").scale(0.7) marriage = Text("It led to the marriage of Esther Klein and George Szekeres", color=YELLOW).scale(0.7) marriage.next_to(story, DOWN) # Final thought final = Text("Open problem: Exact values of N(n) for n ≥ 6 remain unknown", color=BLUE).scale(0.7) final.next_to(marriage, DOWN, buff=1) self.play(Write(story)) self.play(FadeIn(marriage, shift=UP)) self.wait(2) self.play(FadeIn(final, shift=UP)) self.wait(3) # Helper functions from previous example def generate_general_position_points(self, n): points = [] while len(points) < n: new_point = np.round(np.random.uniform(-5, 5, 2), 1) if new_point[0] in [-5, 5]: new_point[0] += np.random.choice([-0.5, 0.5]) if new_point[1] in [-5, 5]: new_point[1] += np.random.choice([-0.5, 0.5]) valid = True for i in range(len(points)): for j in range(i+1, len(points)): for k in range(j+1, len(points)): if self.are_collinear(points[i], points[j], points[k]): valid = False break if valid and not any(np.array_equal(new_point, p) for p in points): points.append(new_point) return points def are_collinear(self, a, b, c): return abs((b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])) < 1e-6