[Tutorial] Finding inclusion hierarchy among circles — An implementation of a sweep-line algorithm

Revision en1, by Arpa, 2022-01-07 11:28:22

Hello Codeforces!

I'm glad to write a tutorial post again after several years. I'm here to present an implementation for an algorithm that calculates inclusion hierarchy among circles. The main article can be found here. The repository where the implementation can be found is here.

The problem

Consider $$$n$$$ non-intersecting circles. Some circles can be inside of others. We need to make a tree of these $$$n$$$ circles such that if $$$i$$$-th circle is inside of $$$j$$$-th circle, the $$$i$$$-th vertex be in the subtree of $$$j$$$-th vertex. For example:

Examples

Algorithm description summary

Move the sweep-line from left to right. At each $$$x$$$, the sweep-line intersects with some circles in some segments of $$$y$$$. These segments are non-intersecting but some of them could be inside of other ones. We need to dynamically keep the order of these segments in our set (e.g. std::set in C++) and when sweep-line sees a new circle, we can find the parent of this circle in the set using a binary search (lower_bound in C++).

You can find the details in the main article or the implementation.

Tags computational geometry, sweep line

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Arpa 2022-01-07 15:03:59 333 (published)
en1 English Arpa 2022-01-07 11:28:22 1670 Initial revision (saved to drafts)