2026 GIS Cup

Problem Description

Motivation

With an ever-growing need for bandwidth, communication standards such as 5G and 6G utilize higher frequencies which allow for faster network speeds. However, a trade-off that comes with higher frequencies is that the signal is more easily blocked by obstacles such as buildings and trees. Thus, considering the line of sight from antennas to customers and how best to arrange the network is an important problem. This year’s contest will focus on applying GIS techniques to optimize the distribution of antennas to best serve an urban environment.

Participants will consider the problem in two-dimensional Euclidean space. Given a collection of building footprints, teams will develop programs to determine where to place a number of antennas on the sides of buildings to maximize the number of buildings that can be serviced. For a building to be serviced, we do not require the entire building to be visible from an antenna, but only a sufficient fraction to be covered; some dead spots are okay, but if there are too many, customers will complain. Formal definitions are provided in the following section.

For this year’s contest, each team will utilize a subset of building footprints from the GlobalMLBuildingFootprints dataset. We will publish a sample dataset of building footprints projected into a planar coordinate system. The dataset will be simplified to only contain simple polygons, i.e. the polygons will not self-intersect and will not have holes. Along with the dataset of building footprints, the program should also take as parameters the number of antennas to be placed as well as a value in \((0,1]\) that specifies what percentage of a building’s perimeter must be covered by the antenna array to be counted as serviced by the network.

By March 31st a sample dataset will be published for teams to use when developing and testing their programs.

On August 15th dataset for evaluation will be published. In addition to the building footprints, three threshold values and three values for the number of antennas to be placed will be provided. Participants will have 24 hours to run their programs and submit their results for each of the nine combinations of threshold values and number of antennas. Participants will also submit their source code for verification and evaluation. Finalist teams will be invited to submit a report describing their solution approach and present at the conference. At least one member of each finalist team must register and attend the conference.

Important dates

Email

You may contact the organizers by email: either Aaron Lowe (alowe) or Ashwin Shashidharan (ashashidharan) both at esri.com.

Problem definition

Before describing the problem formally, we first provide some background definitions. Note that the definitions are in terms of standard Euclidean geometry. We begin by defining what it means for points to be visible to one another.

Definition 1. Given points \(p, q\) in the plane and a set of building footprints \(\mathcal{B}\), represented as simple polygons in the plane, we say \(p\) is visible from \(q\) with respect to \(\mathcal{B}\) if the straight line connecting \(p\) and \(q\) does not intersect the interior of any building.

Figure 1: When the line between points is tangent to a building, this does not block visibility. For example \(p\) is visible from \(s\) as the line between them is tangent to an edge. Similarly \(q\) is visible from \(r\) as the line connecting them only intersects the boundary at a vertex. In contrast, \(r\) is not visible from \(s\) as the line intersects the interior of the building.

Now, we can define what it means for a line segment to be visible from a set of points.

Definition 2. Given a set of points \(\mathcal{P}\) in the plane, a set of building footprints \(\mathcal{B}\), and a line segment \(\ell\), we say that \(\ell\) is visible from \(\mathcal{P}\) with respect to \(\mathcal{B}\) if every point along \(\ell\) is visible from at least one point in \(\mathcal{P}\).

Figure 2: The line segment \(\overline{AB}\) is visible from the set of points \(\{p_1, p_2, p_3\}\) as every point along the segment is visible from at least one of the three points.

The service coverage of a building is then defined to be how much of its perimeter is visible from the set of antennas.

Definition 3. Given a set of points \(\mathcal{P}\) in the plane, a set of building footprints \(\mathcal{B}\), and a building \(b \in \mathcal{B}\), the boundary of \(b\) can be subdivided into visible and non-visible line segments. The coverage of \(b\) from \(\mathcal{P}\) with respect to \(\mathcal{B}\), denoted as \(C_{\mathcal{P}, \mathcal{B}}(b)\), is the ratio of the length of visible segments on the boundary to the total perimeter of \(b\).

Figure 3: Three examples of the coverage of a building, with the visible boundary highlighted in red.

Given the coverage of individual buildings, we can finally define a score for an arrangement of antennas. Given a threshold coverage value that buildings must meet in order to be considered in service, the score for a set of antennas is the number of buildings that meet or exceed the threshold.

Definition 4. Given a set of building footprints \(\mathcal{B}\) and a threshold value \(0 < \tau \leq 1\), the service score of a set of points \(\mathcal{P}\) is the number of buildings \(b_i \in \mathcal{B}\) such that \(C_{\mathcal{P}, \mathcal{B}}(b_i) \geq \tau\).

With these definitions, we can now describe the problem teams are tasked with solving. Teams will be provided with a set of building footprints \(\mathcal{B}\), a threshold \(\tau \in (0, 1]\) representing the desired coverage level, and a parameter \(k\) representing the number of antennas, represented as points, to be placed. We further require the antennas to be placed on the perimeter of building footprints. Teams will try to optimize the service score given these constraints.

Definition 5. Given a set of building footprints \(\mathcal{B}\), a threshold value \(0 < \tau \leq 1\), and parameter \(k\), compute a set of \(k\) points \(\mathcal{P}\) that lie on the boundary of buildings in \(\mathcal{B}\) that maximizes the service score.

Computing the set of positions that achieves the absolute maximum service score is a hard problem, so we expect teams will design their programs to find an approximate best solution given reasonable time and resource constraints.

Figure 4: With \(k=3\) and \(\tau = 0.5\) this placement of antennas {a, b, c} has a service score of 8. Each building has its coverage labeled, with those satisfying the threshold value marked in bold.
Figure 5: With \(k=3\) and \(\tau = 0.6\) this placement of antennas {a, b, c} has a service score of 4. Each building has its coverage labeled, with those satisfying the threshold value marked in bold.

The competition will consist of one set of building footprints \(\mathcal{B}\). Three threshold values \(\tau\) and three values of k will be provided and teams will be tasked with finding the placement of antennas that maximizes the service score for each of the nine combinations of parameters.

Submission and Evaluation

Submission Instructions

Your submission should be a zip file including the following:

  1. A text file with the solutions for each of the sub-problems. Recall that there will be 9 sub-problems, with different parameters for the desired coverage threshold and number of antennas placed. The exact format will be specified when we share the sample dataset. There should be three lines for each of the 9 sub-problems:
    1. The pair of parameters (τ, k).
    2. A comma-separated list of the k coordinates representing the antenna placement for the above parameters: \((x_1, y_1), (x_2, y_2), ... (x_k, y_k)\).
    3. A comma-separated list of the ID of each building you claim is serviced.
  2. A folder that has your source code, along with instructions for compiling and running the program.

Recall these points must lie on the boundary of buildings. To ensure evaluation results match your internal evaluations, please make sure your results remain at 64-bit precision; we will be using standard IEEE 754 doubles.

Evaluation Criteria

For each of the nine combinations of parameters, teams will receive points based on their service score. The point value for each parameter combination will be your service score divided by the highest service score among all submitted answers.

For example, consider the following smaller case with only four sub-problems - two threshold values: 0.3 and 0.6; and two values of k:100 and 500. We see below the service scores and corresponding points that teams A, B, and C receive.

(τ, k)Team ATeam BTeam C
(0.3, 100)200150175
(0.3, 500)150010001000
(0.6, 100)9010080
(0.6, 500)7508001000
(τ, k)Team ATeam BTeam C
(0.3, 100)10.750.875
(0.3, 500)10.660.66
(0.6, 100)0.910.8
(0.6, 500)0.750.81
Total Score:3.653.213.34
Final ranking:
🥇 Team A
🥈 Team C
🥉 Team B

Sample Dataset

As you test your programs, we encourage participants to experiment with different values. The above values are just an example.

FAQ

Q: Is registration required for the GIS Cup?

A: Formal registration is not required to submit a solution to the GIS Cup - however an email to the organizers is appreciated so we can gauge interest. Please note that at least one member of each finalist team will be required to register and attend the conference to present your solution.

Q: Where should solutions be submitted?

A: The webpage will be updated closer to the competition time to include a link to submit.

Q: Can we use AI to implement and test solutions?

A: Yes, you can use any software or code, but please describe it in your short paper if you are invited.