Regions and polygons boundaries for beam-layout optimization Polygons_Boundaries-BL_Optimization

This directory contains a collection of benchmark instances for the beam-layout optimization problem in a satellite telecommunication context. Each instance represents a different geographical region on the earth surface, divided into a set of polygons. The use cases differ from their geographical positions and number of polygons and are designed for algorithmic experimentation and to evaluate optimization methods.

The dataset is organized into individual instance folders, where each folder follows a standardized format and includes multiple representations of the same spatial data to support different processing and visualization needs.

Each instance directory contains the following files:

• regions_long_lat.geojson
  This file stores the geographical coordinates of the points or regions to be covered, expressed as longitude and latitude in standard GeoJSON format. It is primarily intended for vizualization.
• regions_long_lat.geojson
  This file provides the same spatial information using the GeoJSON format, with coordinates expressed as (thx, thy). It is primarily intended for algorithm processing.

The file Instances_characteristics.xlsx summarizes the main properties of all instances and provides indicators of their relative difficulty.

Since computing the full beam database can be computationally prohibitive for large instances, a simplified yet informative approach is adopted. The difficulty of an instance is evaluated by:

• constructing the reflector graph considering only beams that cover a single polygon;
• extracting key graph-theoretic and geometric metrics from this reduced model.

The resulting values serve as lower bounds for the complete beam-layout optimization problem. In particular, the Squared Radius Sum (SRS) obtained from this restricted setting is guaranteed to be no larger than the SRS of any feasible solution covering all polygons.

The spreadsheet includes the following columns:

• Instance: name of the instance
• Nb polygons: number of regions or polygons to be covered
• Nb edges: number of edges in the reflector graph when considering only beams covering one polygon
• Chromatic number: chromatic number of the reflector graph under the same restriction
• Max radius (Lower bound): lower bound on the maximum beam radius required to cover a single polygon
• SRS (Lower bound): lower bound on the Squared Radius Sum for beams covering only one polygon

These metrics provide valuable insight into the structural complexity and expected difficulty of each instance.

All instances are defined under a common set of parameters:

• Number of reflectors: 4
  This value represents a practical compromise between satellite payload weight and communication performance.
• Kappa (κ):
  Kappa is a scaling factor that increases the beam size in order to model the projection of the radio-frequency source placement on the antenna. This enlargement makes it possible to identify beams that are incompatible when assigned to the same reflector.
• Minimum beam radius (smin):
  The minimum allowable beam radius is set to 0.1, based on satellite antenna analysis constraints, guaranteeing physical feasibility.