Source author record

Christian Scheffer

Christian Scheffer appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computational Geometry Data Structures and Algorithms Computer Vision Graphics

Catalog footprint

What is connected

6works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Packing Squares into a Disk with Optimal Worst-Case Density

We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $δ=\frac{8}{5π}\approx 0.509$. This implies that any set of (not necessarily equal) squares of total area $A \leq \frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $\varepsilon>0$ there are sets of squares of total area $\frac{8}{5}+\varepsilon$ that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square $\left(\frac{1}{2}\right)$, circles in a square $\left(\fracπ{(3+2\sqrt{2})}\approx 0.539\right)$ and circles in a circle $\left(\frac{1}{2}\right)$ have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.

preprint2022arXiv

Particle-Based Assembly Using Precise Global Control

In micro- and nano-scale systems, particles can be moved by using an external force like gravity or a magnetic field. In the presence of adhesive particles that can attach to each other, the challenge is to decide whether a shape is constructible. Previous work provides a class of shapes for which constructibility can be decided efficiently when particles move maximally into the same direction induced by a global signal. In this paper we consider the single step model, i.e., a model in which each particle moves one unit step into the given direction. We restrict the assembly process such that at each single time step actually one particle is added to and moved within the workspace. We prove that deciding constructibility is NP-complete for three-dimensional shapes, and that a maximum constructible shape can be approximated. The same approximation algorithm applies for 2D. We further present linear-time algorithms to decide whether or not a tree-shape in 2D or 3D is constructible. Scaling a shape yields constructibility; in particular we show that the $2$-scaled copy of every non-degenerate polyomino is constructible. In the three-dimensional setting we show that the $3$-scaled copy of every non-degenerate polycube is constructible.

preprint2020arXiv

Worst-Case Optimal Covering of Rectangles by Disks

We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $λ\geq 1$, the critical covering area $A^*(λ)$ is the minimum value for which any set of disks with total area at least $A^*(λ)$ can cover a rectangle of dimensions $λ\times 1$. We show that there is a threshold value $λ_2 = \sqrt{\sqrt{7}/2 - 1/4} \approx 1.035797\ldots$, such that for $λ<λ_2$ the critical covering area $A^*(λ)$ is $A^*(λ)=3π\left(\frac{λ^2}{16} +\frac{5}{32} + \frac{9}{256λ^2}\right)$, and for $λ\geq λ_2$, the critical area is $A^*(λ)=π(λ^2+2)/4$; these values are tight. For the special case $λ=1$, i.e., for covering a unit square, the critical covering area is $\frac{195π}{256}\approx 2.39301\ldots$. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

preprint2016arXiv

New Geometric Algorithms for Fully Connected Staged Self-Assembly

We consider staged self-assembly systems, in which square-shaped tiles can be added to bins in several stages. Within these bins, the tiles may connect to each other, depending on the glue types of their edges. Previous work by Demaine et al. showed that a relatively small number of tile types suffices to produce arbitrary shapes in this model. However, these constructions were only based on a spanning tree of the geometric shape, so they did not produce full connectivity of the underlying grid graph in the case of shapes with holes; designing fully connected assemblies with a polylogarithmic number of stages was left as a major open problem. We resolve this challenge by presenting new systems for staged assembly that produce fully connected polyominoes in O(log^2 n) stages, for various scale factors and temperature τ = 2 as well as τ = 1. Our constructions work even for shapes with holes and uses only a constant number of glues and tiles. Moreover, the underlying approach is more geometric in nature, implying that it promised to be more feasible for shapes with compact geometric description.

preprint2015arXiv

Approximating the Integral Fréchet Distance

A pseudo-polynomial time $(1 + \varepsilon)$-approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves $T_1$ and $T_2$. In particular, the running time is upper-bounded by $\mathcal{O}( ζ^{4}n^4/\varepsilon^{2})$ where $n$ is the complexity of $T_1$ and $T_2$ and $ζ$ is the maximal ratio of the lengths of any pair of segments from $T_1$ and $T_2$. The Fréchet distance captures the minimal cost of a continuous deformation of $T_1$ into $T_2$ and vice versa and defines the cost of a deformation as the maximal distance between two points that are related. The integral Fréchet distance defines the cost of a deformation as the integral of the distances between points that are related. The average Fréchet distance is defined as the integral Fréchet distance divided by the lengths of $T_1$ and $T_2$. Furthermore, we give relations between weighted shortest paths inside a single parameter cell $C$ and the monotone free space axis of $C$. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.

preprint2013arXiv

Similarity of Polygonal Curves in the Presence of Outliers

The Fréchet distance is a well studied and commonly used measure to capture the similarity of polygonal curves. Unfortunately, it exhibits a high sensitivity to the presence of outliers. Since the presence of outliers is a frequently occurring phenomenon in practice, a robust variant of Fréchet distance is required which absorbs outliers. We study such a variant here. In this modified variant, our objective is to minimize the length of subcurves of two polygonal curves that need to be ignored (MinEx problem), or alternately, maximize the length of subcurves that are preserved (MaxIn problem), to achieve a given Fréchet distance. An exact solution to one problem would imply an exact solution to the other problem. However, we show that these problems are not solvable by radicals over $\mathbb{Q}$ and that the degree of the polynomial equations involved is unbounded in general. This motivates the search for approximate solutions. We present an algorithm, which approximates, for a given input parameter $δ$, optimal solutions for the \MinEx\ and \MaxIn\ problems up to an additive approximation error $δ$ times the length of the input curves. The resulting running time is upper bounded by $\mathcal{O} \left(\frac{n^3}δ \log \left(\frac{n}δ \right)\right)$, where $n$ is the complexity of the input polygonal curves.