Triangle Packing Strategies within a Rectangle
We address a practical variant of the triangle packing problem: reassembling triangles-originally derived from a Delaunay triangulation of a rectangle-after arbitrary translations and rotations, without overlap, to maximize the covered area. Since triangle packing is an NP-hard problem, we examine four lightweight heuristics that combine translation, rotation, and simple selection rules: (1) grid-guided adjacency, (2) decreasing-area edge joining, (3) random-order edge joining, and (4) length-matching edge joining. Experiments on Delaunaygenerated datasets with 20-60 points show that Strategy 4 achieves the highest average coverage but with greater variance, while Strategy 2 provides the most stable performance. Coverage, runtime, and efficiency metrics demonstrate that even simple geometric heuristics-particularly edge-length matching and edge joining-serve as effective baselines for fast reassembly of triangulated rectangular domains.