Overview
This research investigates the problem of bicriteria polygon aggregation, which involves covering a specified set of polygons with disjoint representative regions. This process simultaneously induces a clustering of the input polygons. The objective function for this problem targets the minimization of a weighted sum comprising the total area and the total perimeter of the generated regions. This formulation builds upon existing 'fencing problems' and finds relevance in applications such as geographical information systems.
Research Context
The problem of bicriteria polygon aggregation, particularly concerning the minimization of a weighted sum of total area and perimeter, has been previously examined. However, prior investigations were restricted to a variant where the boundary curves of the representative regions were constrained to be selected from a fixed subdivision of the plane. A key question in this domain has been whether the problem remains tractable when this restriction is lifted, permitting the output regions to be bounded by arbitrary curves rather than being confined to predefined structures.
Approach
The study provides an algorithm designed to handle bicriteria polygon aggregation with arbitrary shapes. A core aspect of the approach involved fully characterizing the nature of optimal solutions. This characterization revealed that the boundaries of these optimal solutions are composed of constituent elements: specifically, input edges and circular arcs of a constant radius.
In addition to the primary algorithm for arbitrary shapes, the research also considers the parametric variant of the problem. This variant seeks an optimal solution for every possible weighting factor, representing different trade-offs between area and perimeter. For this parametric problem, the researchers demonstrate that $\mathcal{O}(n^2)$ combinatorial solutions are sufficient to describe all optimal solutions across the entire range of weighting factors. The study develops both an exact algorithm and an approximation scheme to address this. To enhance practical scalability, the researchers developed engineering techniques that leverage structural properties inherent to the solutions.
Findings
- The study offers a positive answer to the tractability question for bicriteria polygon aggregation with arbitrary shapes, providing an algorithm with a runtime complexity of $\mathcal{\tilde{O}}(n^4)$, where $n$ represents the number of input vertices.
- Optimal solutions for this problem are characterized by boundaries that are composed of input edges and circular arcs of a constant radius.
- For the parametric version of the problem, where optimal solutions are sought across all possible weighting factors for area and perimeter, $\mathcal{O}(n^2)$ combinatorial solutions are adequate to describe the full set of optimal outcomes.
- Experimental evaluations conducted on real-world data indicated that the developed algorithms exhibit linear runtime performance in practice, including for the parametric variant.
Why This Matters
The problem of polygon aggregation has applications in geographical information systems. The development of an algorithm that handles arbitrary shapes for representative regions, coupled with an objective function that balances area and perimeter, extends the practical utility for tasks requiring the clustering and summarization of polygonal data in such systems.