A fast constructive algorithm for large-scale generation of orthogonal polygonal structures with applications to benchmarking geometric algorithms

Abstract

Efficient generation of large-scale structured data plays an important role in simulation and performance evaluation of algorithms. However, constructing complex geometric instances with guaranteed validity and a prescribed size remains computationally challenging. In this paper, we propose a simple and efficient constructive algorithm for generating orthogonal polygonal structures with a fixed number of vertices. The algorithm incrementally evolves a seed configuration using local transformations, while ensuring structural validity and exact control over the number of vertices. The method runs in polynomial time, and its correctness and complexity are formally analyzed. Experimental results demonstrate that the proposed method substantially outperforms the two baseline algorithms, Inflate-Cut and Inflate-Paste (Tomas and Bajuelos, 2004), in both runtime and memory consumption. For instances with 𝑛 = 5 0 , 0 0 0 vertices, the proposed method requires approximately 11.45 s, whereas Inflate-Cut takes about 38 min, corresponding to a speedup of approximately 200 times. Under the same experimental environment, in which all three algorithms were evaluated on the same computer configuration, the proposed method remains computationally feasible for instances containing up to one million vertices. In contrast, Inflate-Paste becomes impractical beyond approximately 5, 000 vertices, while Inflate-Cut is limited to approximately 50, 000 vertices. The proposed method also requires substantially less memory than the baselines across the tested instances. Furthermore, nearest-neighbor-based uniformity measures indicate that the generated vertices are more evenly distributed over the normalized spatial domain. In addition, the generated datasets are used to benchmark representative algorithms for orthogonal hull computation and minimum-area rectilinear convex hull computation, providing empirical insights into their performance on large-scale inputs. These results demonstrate that the proposed algorithm is an effective tool for large-scale data generation, simulation, and benchmarking of geometric and computational algorithms.

The authors' abstract, as published at the source. Applied Mathematics and Computation, 2026 · DOI ↗