Master's Thesis: Split Packing

Circle packing algorithms
2016-06-01 (last update: 2018-07-20) / Sebastian Morr / CC BY-SA 4.0 / document, paper, talk, cs, art, fav

This page links to a number of scientific texts, which all were a result of my 2016 Master’s Thesis: The thesis itself (which is the most complete version), a paper presented at SODA ‘17, a paper presented at WADS 2017, and a journal article which appeared in the Discrete & Computational Geometry journal.

Master’s Thesis

The full name of my master’s thesis is Split Packing: An Algorithm for Packing Circles with up to Critical Density. It covers a topic from the field of Computational Geometry: Packing circles into various containers, like squares and triangles.

In the thesis, I invented an algorithm which can pack circles and other objects into these containers, if their combined area does not exceed certain bounds. The special property of the algorithm is that these bounds are tight: For any larger area bound, there are circle instances which can not be packed.

The thesis contains a large number of figures, I’d like to invite you to take a look! :-)

Thesis Presentation

For the presentation I created a nonverbal description of the central algorithm in the style of IKEA assembly instructions. (Later, in 2017, I started a whole series of these, the IDEA project.)

SPLIT-PÄCK

Also, while working on this thesis, I wrote an interactive visualization tool called Circus, which I used as a personal thinking and explaining tool. You can try it out by clicking on the image below, usage instructions are located in the lower left. The tool is written in CoffeeScript and uses the HTML5 canvas for drawing, the source code is on GitHub.

Screenshot of the Circus visualization tool

SODA paper

A solo-authored paper version of the thesis, condensed to 10 pages, and lovingly typeset. I presented this paper at the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017) in Barcelona. It only covers packing circles into square containers.

http://dl.acm.org/citation.cfm?id=3039686.3039693

WADS paper

This paper covers packing circles into triangular containers. I presented it at the 15th Algorithms and Data Structures Symposium (WADS 2017) in St. John’s, Canada.

https://doi.org/10.1007/978-3-319-62127-2_32

DCG article

This article combines the two paper versions. You can read the preprint at arXiv.org, or a view-only version of the published article.


Comments?

Send a tweet to @blinry or drop me a mail at sebastian@morr.cc. If you enjoyed this, please consider supporting me on Patreon!