我要吃瓜

Citation

Kashyap G, Malik K, Wazir S & Brownlee A (2025) Optimization of the rectangle area inside a concave polygon using PSO and Tabu Search. Soft Computing. https://doi.org/10.1007/s00500-025-10568-1

Abstract
Optimising a figure inside any shape is an important problem with many applications. Several studies tried to find the largest area of the rectangle inside the convex polygon in mathematics, as there are polynomial-time solutions available i.e. there exists an algorithm for finding the solution bounded by a polynomial function, but not for concave polygon as there are no polynomial-time solutions available. This makes this problem an NP (Nondeterministic Polynomial)-complete problem. Generally, the availability of the solution depends upon the length of the input for the problem. However, when solving an NP-complete problem, one method is to apply a polynomial algorithm to estimate the solution; the result will not always be optimal, but it will be close. Therefore, this paper attempts to find the maximum area of the rectangle inside the non-convex polygon by using two heuristic algorithms that are: 1) PSO (Particle Swarm Optimization), and 2) Tabu Search. Where Tabu Search has been utilised for comparative purposes to demonstrate the PSO's exceptional performance. These two algorithms work fast and find the optimal rectangle more efficiently than conventional mathematical approaches. These approximation algorithms have an O(n3) time complexity and O(n2) space complexity for PSO, and O(n4) time complexity and O(n2) space complexity for Tabu Search. In addition to this, the already available literature is also employed for comparative purposes, with PSO displaying competitive results.

Keywords
Area; Concave; Computational geometry optimization; PSO; Polygon; Rectangle; Tabu search