Structured Discrete Shape Approximation: Theoretical Complexity and Practical Algorithm
We consider the problem of approximating a two-dimensional shape contour (or curve segment) using discrete assembly systems, which allow to build geometric structures based on limited sets of node and edge types subject to edge length and orientation restrictions. We show that already deciding feasibility of such approximation problems is NP-hard, and remains intractable even for very simple setups. We then devise an algorithmic framework that combines shape sampling with exact cardinality-minimization to obtain good approximations using few components. As a particular application and showcase example, we discuss approximating shape contours using the classical Zometool construction kit and provide promising computational results, demonstrating that our algorithm is capable of obtaining good shape representations within reasonable time, in spite of the problem's general intractability. We conclude the paper with an outlook on possible extensions of the developed methodology, in particular regarding 3D shape approximation tasks.
Code available per request.
@article{TILLMANN2021101795,
title = {Structured discrete shape approximation: Theoretical complexity and practical algorithm},
journal = {Computational Geometry},
volume = {99},
pages = {101795},
year = {2021},
issn = {0925-7721},
doi = {https://doi.org/10.1016/j.comgeo.2021.101795},
url = {https://www.sciencedirect.com/science/article/pii/S0925772121000511},
author = {Andreas M. Tillmann and Leif Kobbelt},
keywords = {Shape approximation, Discrete assembly systems, Computational complexity, Mixed-integer programming, Zometool},
abstract = {We consider the problem of approximating a two-dimensional shape contour (or curve segment) using discrete assembly systems, which allow to build geometric structures based on limited sets of node and edge types subject to edge length and orientation restrictions. We show that already deciding feasibility of such approximation problems is NP-hard, and remains intractable even for very simple setups. We then devise an algorithmic framework that combines shape sampling with exact cardinality minimization to obtain good approximations using few components. As a particular application and showcase example, we discuss approximating shape contours using the classical Zometool construction kit and provide promising computational results, demonstrating that our algorithm is capable of obtaining good shape representations within reasonable time, in spite of the problem's general intractability. We conclude the paper with an outlook on possible extensions of the developed methodology, in particular regarding 3D shape approximation tasks.}
}
