jeroenodb's blog

12 Cool Geometry problems
By jeroenodb, 11 days ago, In English

Cool and geometry in the same sentence? You must be mad! Well, no. I think there are lots of interesting geometry problems, only the average geometry problems people know happen to be implementation-heavy (and frankly not that cool) problems from ICPC contests. Here is a list to show off some actually cool problems. I included some problems to have some variation in the different kinds of problems on the list. The stars indicate approximate difficulty (not coolness per se).

  1. ⭐⭐⭐⭐⭐NCPC 2023 Interwined For this problem there is unfortunately a solution with a complicated datastructure (decremental convex hulls). The coolness is from the fact that it can be solved with just normal convex hull algorithms. Can you figure it out?
  2. ⭐⭐⭐★★ CEOI 2020 1402B - Roads. I remember this problem fondly as CEOI was my first big onsite competition, and this was my first encounter with geometry problems (I couldn't solve it, but I eventually upsolved it). It uses some classical ideas, but it is still quite nice, and the implementation isn't bad.
  3. ⭐⭐⭐★★ Balkan OI 2011 Time Is Money It does not immediately look like geometry. But it features a cool idea.
  4. ⭐⭐⭐★★ IOI 2006 joining points and Bubblecup generalized version. 1045E - Ancient civilizations Although it is not required, you can try for a $$$O(n \log(n))$$$ solution.
  5. ⭐⭐⭐★★ NEERC Southern Subregional 1070M - Algoland and Berland One of my favourite problems.
  6. ⭐⭐★★★ BAPC 2016 Airport Logistics When you have seen this type of problem many times, maybe it becomes less cool. But still cool when seen for the first time. This is one of the problems on the list which unfortunately needs a bit more implementation.
  7. ⭐⭐⭐★★ Project Euler Convex Holes
  8. ⭐⭐⭐⭐★ Yokohama Regional 2019-2020 Fun Regions Definitely not easy to implement, but the idea is great.
  9. ⭐⭐⭐★★ Cameramakers This is actually two problems in one. You definitely need to make some observations to get a good time complexity. But for seasoned geometry enjoyers, it may be too straightforward.
  10. ⭐★★★★ OCPC Delft Contest Curly Palindromes These last three problems are all my own problems. I think they are cool, but that's for you to decide.
  11. ⭐⭐⭐⭐★ ICPC Asia West 2023 Disk Tree
  12. ⭐⭐⭐⭐⭐ OCPC Delft Contest Beer Circuits

Do you agree with this list? Do you have more interesting geometry problems, let me know!

  • Vote: I like it
  • +178
  • Vote: I do not like it

»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jeroenodb (previous revision, new revision, compare).

→ Reply
»
10 days ago, # |
  Vote: I like it +31 Vote: I do not like it

The problem from CEOI 2020, Roads, is in fact an easier version of Exercise 2.13 from "Computational Geometry: Algorithms and applications". Instead of connecting disjoint segments, you're asked to connect disjoint triangles.

→ Reply
»
10 days ago, # |
  Vote: I like it +24 Vote: I do not like it

A bonus problem: I just remembered that I liked 104848I - 1\%-Euclidean a lot. So consider yourself lucky (or unlucky) with a 13th geometry problem.

→ Reply
»
10 days ago, # |
  Vote: I like it -35 Vote: I do not like it

Beginner Question : If there a basic topic list and any blogs/books recommendation to get started on computational geometry for CP. Objective is to understand any problem statement and solve the ones rated less than 2000 may be 1500.

→ Reply
  • »
    »
    7 days ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    i dont know a single computational geomtery problem rated below 2500.There might be but i have never came across one.

    → Reply
»
10 days ago, # |
  Vote: I like it +10 Vote: I do not like it

I really liked TimeisMoney problems, although I don't see it as a Geometry problem :) If you like it, then I want to recommend 2014-2015 ACM-ICPC, Asia Tokyo Regional Contest J. Exhibition.

2015-2016 NEERC Northern K. Kingdom trip is one of my favorite Geometry problem. I usually do not prefer geometry problems, but I like them if it has a nice observation and is not too painful to code.

I want to introduce my problem from ptzcamp. Can you solve it in $$$O(n \log W)$$$ time?

→ Reply
  • »
    »
    10 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I believe for your problem I have an unpractical linear time solution. You can have 4 parameters, $$$a$$$, $$$b$$$, $$$c$$$ and $$$\sqrt ans$$$. The whole problem can then be written as a linear program with 4 dimensions and 2n halfplanes (each quadratic constraint can be exchanged for two linear constraints, by taking the square root. Such linear programs with constant dimension can be solved in linear time.

    → Reply
    • »
      »
      »
      10 days ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      That's correct and actually majority of solvers solved it with LP.. But I prefer the intended solution with O(n log ) time complexity.

      → Reply
»
7 days ago, # |
  Vote: I like it +10 Vote: I do not like it

What's the solution to Intertwined without decremental convex hull?

→ Reply
  • »
    »
    7 days ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Assume for now, the rope segment already starts in such a way such that all the points are to the left of it, and it's already wrapped around at least one point (so if the rope would be very long, it could enclose the convex hull of the point set). Then you can actually do a graham scan.

    So sort the points radially around the rope segment start. Go over these points in order, and for each point $$$p$$$, given the partial hull you have, you have to calculate a tangent to this hull in $$$O(\log(n))$$$ time. If the rope would be too short to reach $$$p$$$ (you can figure this out by keeping prefix sums on the partial hull of the lengths), you ignore this point. Otherwise you do as normal in the graham scan pop some hull points and add $$$p$$$. This process can end in two different ways.:

    • Either we come back to the start, so we have successfully enclosed the hull. Then we can do the length of the rope modulo the length of the hull + for the last iteration go over the hull with brute force, to quickly get to a situation where the rope length gets at least halved.
    • Or we stop at some point with our partial hull, because our graham scan only scans for one full rotation, so it got stuck somewhere. It means we could not go back to the starting point, so also the length of the rope has halved.

    So you can continuously do this procedure for a time complexity of $$$O(n log(n) log(d))$$$.

    How to start the algorithm to get into this general case is an exercise for the reader :)

    For a visualization see: Visualization

    → Reply