Why was I reading about computational geometry?
This is part 2 of 3 of my experience studying computational geometry; you can read the first part here!
One bright day, I’d just finished a Semántica y Verificación class and was walking to the subway, praying to find a free seat to fall asleep on as though I were a massive elephant seal.
Suddenly, I got +20 notis from Google Classroom; I had to choose a paper to present in class.
Thanks to my 58-hours-a-day TikTok doomscrolling skills, I looked over all the papers like a guy who wants to gain knowledge by reading without actually reading. My eyes were moving across dozens of sheets, trying to find out which one was hard enough to feature a marvelous algo, but not too complex to make a fool of myself in front of thousands of researchers! Nah, we were only 6 students and… Jorge Urrutia!? and Adriana Ramírez!? A tad of pressure, ngl.
My heart stopped when I read the word “dynamic”. Why do we need a dynamic algo? Most importantly, what’s a dynamic algo? Am I choosing something that’s totally unknown to me? YES.
They gave us around 3 weeks to prepare everything. I decided to use my lovely Typst and a package called Polylux to create my slides (at the bottom of the page, you can find my work :]).
The paper’s problem
Lemme explain to you in brief terms what the paper is about.
Imagine a bunch of points on a 2D plane, but we can distinguish them by color—some of them are red while others are blue. We want to use a circle to separate them according to certain conditions: we want to find the circle with the smallest radius that encloses all the red points, and that contains the smallest number of blue points.
Maybe you’re saying, “Well… Where’s the dynamic part?” Assume we’re in the middle of a war called “The War of the Biggest LARPers” in the year 3872. Red points are your enemies! (the ones who only use Python imports and show off their projects on X). Blue points are your friends! (the ones who assume what they want to prove). You’ve calculated the perfect circle that destroys every Python buddy… but suddenly one of your mates says, “Hmm… Fortnite released a new season. I gotta go. Good luck on the battlefield!”
Of course, you could execute the same algo (the static one) again. Now! You’re ready to vanquish every soul on earth… until one pal says, “P = NP! Fuck this war! I’m not Grigori Perelman; I’m not rejecting the prize! I’ll hurry!”
Of course, you could execute the same algo (the static one) again. Now! You’re ready to vanquish every sou… I won’t repeat the joke again, you get the point, don’t you?
What if we need to calculate the solution over and over again? It turns out that we can apply a new algo with better time complexity. Thus, we can retrieve the solution quicker under insertions and deletions of points—we’re solving the problem “dynamically” as new inputs arrive.
Tbh, at least for now, I don’t want to write a full entry explaining definitions, algos, edge cases, and so on, but rather just talk about my experience.
I had to read 29 hrs per second
During the first week, I delivered a hands-on masterclass in ego: Did the authors cite another paper to understand why we can assume that there’s no red point that doesn’t belong to the CH, and that there’s no blue point inside the same CH by taking advantage of a Farthest-Point Voronoi Diagram? Then what? Surely a 6th-semester CS student can infer the details under the hood while reading in the middle of a crowded subway at 6am on Monday.
After one day of thinking I was Mark Zuckerberg in 2004, I started reading the paper’s references.
The most important part was that I needed to read a whole new paper besides my chosen one. That sounds common, but the thing was that I “needed” to explain it in class before talking about the main topic. Otherwise, nobody would understand anything. So, I had 2.5 weeks to prepare “two” presentations.
It was fun. I enjoyed every second of that suffering. I didn’t understand some definitions at first until I drew lots of diagrams. I was so nervous on presentation day. Yet, I did what I was cut out for (I’ll conveniently ignore my -458 ELO in LoL from playing Ezreal): talking too much. I got a 9/10.
If you want to take a look at my slides, here you go! They’re written in Spanish, btw. Here you can read the paper.