My first project: Smallest enclosing circle

2022-03-20

Originally posted on my first, React-based site. The demo has since been rewritten in plain SVG, so the Konva and React parts below describe the original.

The following paragraph gives an idea of the given problem:

The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, smallest enclosing circle problem) is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. (Wikipedia)

I learned about this problem in my second semester in the course “Algorithms and Probability”, where we discussed several algorithms on how to solve it. In my project, I decided to implement two easy but elegant randomized algorithms, first a naive randomized algorithm that chooses random points and second an optimized version that “learns” after choosing random points.

When you go to the project, the description of the algorithm can be summarised by following lemma and pseudocode:

For any finite P on a canvas with |P| ≥ 3 there exists a subset Q ⊆ P, such that |Q|=3 and smallest enclosing circle of Q is equal to P.

Naive algorithm:

while
    choose Q ⊆ P with |Q| = |N| randomly
    calculate C(Q)
    if P contained in C(Q) then
        return C(Q)

Smart algorithm:

while
    choose Q ⊆ P with |Q| = |N| randomly
    calculate C(Q)
    if P contained in C(Q) then
        return C(Q)
    double points in P outside of C(Q)

The naive algorithm has an expected runtime of O(n⁴) whereas the smart algorithm has an expected runtime of O(n log n) obtained through probabilistic runtime analysis not covered here.

One thing I struggled a lot with when implementing the algorithms was floating point precision. As the canvas uses integers for position and circle radius, it is hard to implement the circle finding algorithm without floats. Especially when checking whether all points are contained in the circle, there were a lot of imprecisions, thus I provided a rather bandaid fix that will maybe be improved sometime.

For the canvas I used a Javascript library called Konva. At first it was very difficult to use, as documentation for React is poor because the library is mostly managed by one person and is originally designed for plain Javascript. Also, as I know very little about how plain Javascript is used to build websites I had no idea how to translate from Javascript to React. Fortunately, there is a small Discord server where the creator of Konva is active, so for specific questions where I couldn’t find an answer online I had a source for help.

Lastly, feel free to contact me in case you find any bugs regarding the implementation. For every calculation the array of points is printed on the console, so I would be glad if that information was relayed to me as well if the bug applies to the calculation of a circle. Have fun!