I found a heuristic solution that has complexity O(n*log(n)) per

step (for 1000 elements and 16 areas, I got a good solution in 500

steps).

The code has some constraints that are easy to remove:

- All areas must have exactly the same amount of elements
- Distances calculated assuming flat space (just rewrite Point’s

function distance_to)

It’s easy to customize heuristic params and remove those

constraints

Ps.: Not sure about the complexity, you can check yourself, because

I solved the problem during a sleepless, but it’s gone now and I’m

going to bed. If you have some doubts ask me and I’ll answer

tomorrow…

Solution:

class Point

attr_accessor :x, :y, :distances, :at

def initialize(x, y)

@x, @y = x.to_f, y.to_f

end

def distance_to§

Math.sqrt sum_of_squares_to§

end

def sum_of_squares_to§

(self.x-p.x)**2 + (self.y-p.y)**2

end

def calc_distances_to(areas)

@distances = areas.inject({}){ |d, a| d[a] = distance_to a.mean;

d }

end

def self.new_by_rand

Point.new(rand(100), rand(100))

end

def to_s

“(#{x},#{y})”

end

alias :inspect :to_s

end

class Area < Array

def mean

@mean || mean!

end

def entropy

self.inject(0) do |ent, p|

ent += mean.sum_of_squares_to p

end

end

def mean!

ps = self.inject( Point.new(0, 0) ) do |ps, p|

ps.x += p.x

ps.y += p.y

ps

end

ps.x = ps.x/self.size

ps.y = ps.y/self.size

self.sort_by!{ |p| p.distance_to ps }

@mean = ps

end

def fix!

self.each do |p|

p.at = self

end

end

def self.refine(areas, points, n)

area_size = areas.first.size

refresh_distances(areas, points)

doubt_points = areas.inject([]) do |dp, area|

dp.concat area[n…-1]

end

```
doubt_points.each do |point|
point.at.delete point
point.at = nil
end
doubt_points.each do |point|
ordered_areas = point.distances.sort_by{ |k, v| v }
nearest_area, distance = ordered_areas.pop
until(nearest_area.size < area_size)
nearest_area, distance = ordered_areas.pop
end
nearest_area << point
point.at = nearest_area
end
```

end

def self.refresh_distances(areas, points)

areas.each &:mean!

points.each do |p|

p.calc_distances_to areas

end

end

def self.all_areas_same(areas_1, areas_2)

areas_1.each_with_index do |a, i|

return false if areas_2[i] != a

end

return true

end

def self.refine_until_good_solution(areas, points, good_ratio =

0.01, max = 10_000, n = (areas.first.size*0.9).to_i, doubt_region =*

max0.05)

areas, points = areas.clone, points.clone

current_entropy = last_entropy = areas.inject(0){ |ent, a| ent +=

a.entropy }

enhance = 10*good_ratio

count = 0

best_solution = areas.clone

best_entropy = current_entropy

while( count < doubt_region || ( count < max && enhance >

good_ratio ) )

last_entropy = current_entropy

Area.refine areas, points, n

current_entropy = areas.inject(0){ |ent, a| ent += a.entropy }

enhance = (current_entropy - best_entropy)/best_entropy

if best_entropy > current_entropy

best_entropy = current_entropy

best_solution = areas.clone

end

count += 1

puts “Step: #{count}, Enhance: #{enhance}, Entropy:

#{current_entropy}”

end

best_solution.each &:fix!

[ best_solution, best_entropy ]

end

end

# Example:

points = []

areas = 16.times.map do |n|

area = Area.new

(1000/16).times do |i|

p = Point.new_by_rand

p.at = area

area << p

points << p

end

area

end

Area.refine_until_good_solution(areas, points)