The sparsest packing problem emerges in manufacturing multi-hole extrusion dies to obtain small and precise products in the automotive, aviation, food, and medical industries. The goal is to maximize the minimum Euclidean distance between the objects and between the objects to the boundaries of the container. Additionally, this task might be subject to balancing constraints that determine that the deviation of gravity center of the system should stay within a threshold. We present a novel custom environment that encompasses the constraints present in this task. We experiment with the proposed environment using Proximal Policy Optimization to assess the applicability of reinforcement learning for the sparsest packing problem with circular objects in a circular container. Our results indicate that the proposed agent learns efficiently, demonstrating promising results in both finding feasible solutions and optimizing the placement of objects. Our approach not only shows the potential of reinforcement learning for solving the sparsest packing problem but also provides insights into its effectiveness in environments with complex spatial and balancing constraints.

While humans show remarkable proficiency in solving visual puzzles, machines often fall short due to the complex combinatorial nature of such tasks. Consequently, there is a growing interest in developing computational methods for the automatic solution of different puzzles, especially through deep learning approaches. The Tangram, an ancient Chinese puzzle, challenges players to arrange seven polygonal pieces to construct different patterns. Despite its apparent simplicity, solving the Tangram is considered an NP-complete problem, being a challenge even for the most sophisticated algorithms. Moreover, ensuring the generality and adaptability of machine learning models across different Tangram arrangements and complexities is an ongoing research problem. In this paper, we introduce a generative model specifically designed to solve the Tangram. Our model competes favorably with previous methods regarding accuracy while delivering fast inferences. It incorporates a novel loss function that integrates pixel-based information with geometric features, promoting a deeper understanding of the spatial relationships between pieces. Unlike previous approaches, our model takes advantage of the geometric properties of the Tangram to formulate a solving strategy, exploiting its inherent properties only through exposure to training data rather than through direct instruction. Extending the proposed loss function, we present a novel evaluation metric as a better fitting measure for assessing Tangram solutions than previous metrics. We further provide a new dataset containing more samples than others reported in the literature. Our findings highlight the potential of deep learning approaches in geometric problem domains.

Seeded segmentation methods have gained a lot of attention due to their good performance in fragmenting complex images, easy usability and synergism with graph-based representations. These methods usually rely on sophisticated computational tools whose performance strongly depends on how good the training data reflect a sought image pattern. Moreover, poor adherence to the image contours, lack of unique solution, and high computational cost are other common issues present in most seeded segmentation methods. In this work we introduce Laplacian Coordinates, a quadratic energy minimization framework that tackles the issues above in an effective and mathematically sound manner. The proposed formulation builds upon graph Laplacian operators, quadratic energy functions, and fast minimization schemes to produce highly accurate segmentations. Moreover, the presented energy functions are not prone to local minima, i.e., the solution is guaranteed to be globally optimal, a trait not present in most image segmentation methods. Another key property is that the minimization procedure leads to a constrained sparse linear system of equations, enabling the segmentation of high-resolution images at interactive rates. The effectiveness of Laplacian Coordinates is attested by a comprehensive set of comparisons involving nine state-of-the-art methods and several benchmarks extensively used in the image segmentation literature.

We present a simple yet effective snapping technique for constraining the motion of the cursor of an input device to the surface of 3D models whose geometry is arbitrarily deformed by a programmable hardware fragment and vertex processor. The technique works in image space and thus snaps the cursor to the geometry actually rendered instead of the geometry originally submitted to the rendering pipeline. We also present a method to establish a correspondence between snapped geometry in image space and object space, and an efficiency improvement based on the control of frequency of frame buffer accesses. Performance tests are conducted and compared against the standard picking and snapping algorithm used by the D3DX library of the Microsoft Direct3D API. We conclude by emphasizing the feasibility of our algorithm when facing the new advances of the graphics hardware for deforming geometry on the GPU.