Clever algorithm for ordered compact sub-grouping

I have a set of 2D points (called "seats"), with each having a scalar numerical value attached to it.

I have an ordered sequence of groups, each with an integer attributed to it, such that the sum of those integers is the number of seats.

I want to give a group to each seat, such that:

• The number of seats in each group is its integer.
• When calculating the mean scalar value of all the seats of each group, and sorting the groups by that value, they end up in the same order as the initial sequence.
• The compacity of the groups is maximized. The metric I sketched for that (but another one would do as well) is the maximum distance between two points in each group, summed across all groups, and minimized.

I have a bruteforce algorithm, testing all combinations and keeping the best, but it obviously takes ages to compute because the number of combinations is so big. And since so many of them blow up the compacity metric, there's a lot of idiotic combinations that are tested while not deserving to - for example when you have an A - B - A alignment of points, it's obvious that it will be less compact than A - A - B or B - A - A.

So I thought about something based on graph theory and flow, but being based on Python it's not easy, and perhaps not worth, implementing a heavy graph baseline. The idea was to pick g seats (for g groups), give them to each groups in order, then test all the ways of expanding the groups seat by seat untill all is filled. That may span fewer combinations (since only the compact ones are generated), though expanding from several initial seat picks will generate most allocation several times. And computing a neighboring graph that is compact for all possible arrangements of seats is not trivial.

Not having to import anything would be a huge bonus.

Thoughts ?

• Talking about compacity it makes sense to consider a Peano curve filling the room, reorder seats according to such curve and give to each group a contiguous sequence of seats in the new order Commented Jun 24 at 15:33
• @Symlic I'm not sure that would satisfy the condition on ordering the groups. Also the seat placement is chosen by other geometry constraints, I'm not sure how I would make all seats fit to the curve. Commented Jun 25 at 8:18

I would suggest solving this with an ILP solver. To me, I suspect the problem is likely to be NP-hard, so I don't expect there to be a simple algorithm that is efficient and optimal for all inputs. Instead, I think you're more likely to have good results using an ILP solver.

The problem can be formulated as integer linear programming (ILP) as follows. Introduce zero-or-one variables $$x_{s,g}$$, where $$x_{s,g}=1$$ means that seat $$s$$ is assigned to group $$g$$. You can express the following requirements using linear inequalities on these variables:

• Each seat is assigned to only one group. e.g., $$\sum_g x_{s,g}=1$$.
• Each group $$g$$ is assigned a specified number of seats. e.g., $$\sum_{s} x_{s,g}=n_g$$.
• For each pair of groups $$g,g'$$ that are next to each other in the initial sequence, the mean scalar of seats in $$g$$ is greater than the mean scalar of seats in $$g'$$. e.g., $$(\sum_s c_s x_{s,g})/n_g \ge (\sum_s c_s x_{s,g'})/n_{g'}$$, where $$c_s$$ is the scalar associated with seat $$s$$.

Your goal is to minimize the sum of maximum distances is minimized. This can also be expressed as a linear expression of the variables, namely, you want to minimize $$\Phi = \sum_g d_g$$, subject to

$$d(s,t) \le d_g + C (1-x_{s,g}) + C (1-x_{t,g}),$$

where $$d(s,t)$$ is the distance between two seats $$s,t$$ and $$C$$ is a large constant (bigger than distance between the farthest pair of seats). Here $$d_g$$ is a real-valued variable, one per group $$g$$; its intended value is the maximum distance between any pair of points in group $$g$$, and the inequalities above enforce that intention.

Then you can solve this ILP instance with an off-the-shelf ILP solver, and see what it finds for you.

• Thank you for your answer, I'll try to do that when I find the time to clear it up. Commented Jun 27 at 11:54