Computational Geometry
See recent articles
Showing new listings for Friday, 21 August 2026
- [1] arXiv:2608.19910 [pdf, html, other]
-
Title: Polyomino Nets Covering Three Different Boxes of Area 106 and Related ResultsErik D. Demaine, Jenny Diomidova, Nicole Jacobus, Landon Kryger, Matthew T. Parker, Michael Tardibuono, Ryuhei Uehara, Hanyu Alice ZhangComments: 11 pages, 6 figures, presented at CCCG 2026Subjects: Computational Geometry (cs.CG)
We present new results for polyomino nets that fold into 2 and 3 different cuboids through a computer search. The main result is the finding of 40 nets that fold into all three different cuboids with a surface area of 106. The secondary results are the finding of infinite families of nets that fold into three cuboid shapes, and the calculation of the number of common nets between smaller cuboids. The algorithms used to make the searches feasible will also be explained. The algorithms include taking advantage of some hidden structures in the nets that fold into the Nx1x1 cuboids, taking advantage of how a lot of nets fold into cuboid shapes in a 'striped' way, and using a variant of Redelmeier's algorithm. The paper ends with open questions that encourage the reader to broaden our collective understanding of the subject of creating polyomino nets.
New submissions (showing 1 of 1 entries)
- [2] arXiv:2308.05998 (replaced) [pdf, html, other]
-
Title: Solving Proximity Problems for Polygonal Shapes via PolynomialsComments: This manuscript combines the results of two separate works: Solving Fréchet Distance Problems by Algebraic Geometric Methods (arXiv:2308.14569) which appeared as an extended abstract in the proceedings of SODA 2024 and Simplified and Improved Bounds on the VC-Dimension for Elastic Distance Measures (arXiv:2308.05998)Subjects: Computational Geometry (cs.CG)
We study range spaces, where the ground set consists of either polygonal curves in $\mathbb{R}^d$ or polygonal regions in the plane that may contain holes and the ranges are balls defined by distance measures, such as the Hausdorff distance, the Fréchet distance and the dynamic time warping distance. These range spaces appear in various applications like classification, simplification, range searching, density estimation and clustering when the instances are trajectories, time series or polygons. We show for the Fréchet distance of polygonal curves and the Hausdorff distance of polygonal curves and planar polygonal regions that the VC-dimension is upper-bounded by $O(dk\log(km))$, where $k$ is the complexity of the center of a ball, $m$ is the complexity of each polygonal curve or region in the ground set, and $d$ is the ambient dimension. For $d \geq 4$ this bound is tight in each of the parameters $d,k$ and $m$ separately. For a variant of dynamic time warping distance of polygonal curves using squared distances, our analysis directly yields an upper-bound of $O(\min(dk^2\log(m),dkm\log(k)))$. We also obtain exact solutions that are hitherto unknown for simplification, range searching, nearest neighbor search, and distance oracle.
- [3] arXiv:2506.09726 (replaced) [pdf, html, other]
-
Title: Don't be Afraid of Cell Complexes! An Introduction from an Applied PerspectiveComments: 51 pages, 16 figures (plus appendix)Subjects: Signal Processing (eess.SP); Computational Geometry (cs.CG); Social and Information Networks (cs.SI); Algebraic Topology (math.AT)
Cell complexes (CCs) are a higher-order network model deeply rooted in algebraic topology that has gained interest in signal processing and network science recently. The processing of signals supported on CCs can be described in terms of easily-accessible algebraic or combinatorial notions. However, the commonly presented definition of CCs is grounded in abstract concepts from topology and remains disconnected from the signal processing methods developed for CCs. In this paper, we aim to bridge this gap by providing a simplified definition of CCs that is accessible to a wider audience and can be used in practical applications. Specifically, we first introduce a simplified notion of abstract regular cell complexes (ARCCs). These ARCCs only rely on notions from algebra and are equivalent to regular cell complexes for most practical applications. Second, using this new definition we provide an accessible introduction to (abstract) cell complexes from a perspective of network science and signal processing, including an introduction to central methods and recent developments. Furthermore, as many practical applications work with CCs of dimension 2 and below, we provide an even simpler definition for this case that significantly simplifies understanding and working with CCs in practice.
- [4] arXiv:2512.18268 (replaced) [pdf, html, other]
-
Title: On Minimum Aerial Photographs for Planar Region Coverage: Hardness and ApproximationSubjects: Robotics (cs.RO); Computational Geometry (cs.CG)
Aerial photography with drones often requires covering a planar region with a limited number of images while maximizing image resolution, equivalently minimizing the footprint size of each photograph. We study this task as covering a simple planar polygon with k equal squares or circles of minimum size, including the practically relevant variant in which photograph centers must lie inside the region or on its boundary. We prove that approximating the minimum square side length is NP-hard within a factor of 1.165, and within a factor of 1.25 when square centers are restricted to the region; together with known hardness for circle coverage, these gaps establish strong intractability for aerial coverage planning. We further give a (2\sqrt{2} + \epsilon)-approximation algorithm for square coverage via sampling and farthest-point clustering under the L_\infty metric, which also applies under the center-location constraints. Beyond aerial surveying, the results inform related geometric covering tasks such as facility and sensor placement.