Bounding box fusion with constraints

I have N bounding boxes that I want to fuse/merge given some constraints. Each bounding box has a label.

Goal: The main goal is to minimize N.

Constraints:

1. Bounding boxes with the same label can be grouped together

2. A new bounding box resulting from a fusion can't overlap a bounding box with a different label:

How can this be solved ? Is it related to a classic OR problem ?

1 Answer

You can solve this as a graph coloring problem in a graph with one node per original box and an edge between each pair of nodes for which the corresponding boxes cannot be merged (either because they have different labels or because merging would conflict with a box of a different label). Each color corresponds to a new bounding box, adjacent nodes cannot be the same color, and you want to minimize the number of colors.