How to allow a max Manhattan distance between all the points in a group

Question

I have a 2D-array in which I want to make groups where all the points in a group have a max Manhattan distance between them. The groups can be disjoint. For example, from this starting array (10 x 10):

[[ 67  97  72  35  73  77  80  48  21  34]
 [ 11  30  16   1  71  68  72   1  81  23]
 [ 85  31  94  10  50  85  63  11  61  69]
 [ 64  36   8  37  36  72  96  20  91  19]
 [ 99  54  84  56   3  80  41  45   1   8]
 [ 97  88  21   8  54  55  88  45  63  82]
 [ 13  53   1  90  39  28  48  15  86   8]
 [ 26  63  36  36   3  29  33  26  54  58]
 [ 74  40  53  12  21  17   4  87  14  22]
 [ 23  98   3 100  85  12  65  21  83  97]]

I should be able to divide it into different groups.

I currently have a function that finds the possible points I could add to a group with a starting point (here munip is the first point of the group):

def possible_munips(x, y, munip, dist_manhattan_max, temp_array):
    list = []
    for i in range(y):
        for j in range(x):
            if (j, i) != munip and munipIsValid(j, i, munip, dist_manhattan_max) and temp_array[i][j] != -1:
                list.append((j, i, temp_array[i][j]))

I iterate through an 2D-array, temp_array, in which the points that have already been put in a group have their value set to -1. munipIsValid checks if the point is at a max Manhattan distance from the starting point.

I then just add one by one the points until I've reached the desired length (k) of a group and I make sure every time I add a new point to a group, the group stays valid, like this:

munips = possible_munips(x, y, munip, dist_manhattan_max, temp_array)

while len(new_group) < k:
    point = munips[0]
    new_group.append(point)
    if not groupIsValid(new_group, distManhattanMax, len(new_group)):
        new_group.remove(point)
    munips.remove(point)
    current_sol.append(new_group)

for groups in current_sol:
    for munip in groups:
        temp_array[munip[1], munip[0]] = -1

I've also tried adding a swapping function which tries to swap points between groups in order to make both of them valid. But sometimes it doesn't find a solution and I'm left with and invalid group.

My understanding: we have a list of coordinates `C`. We can perform Manhattan distance between two coordinates `P` and `Q`. What do you want to make from here? — Bruno Peixoto, Dec 01 '22 at 16:10
I want to make groups of points, where all the points in the group are at a max manhattan distance. Let says in this example, if I wish to make 9 groups, I would then make 5 groups of 6 points and 4 groups of 5 points. — Antoine Descombes, Dec 01 '22 at 17:21
You have 10 points and wish to build a certain group quantity. It does not match the resulting cardinality of your explanation. If I understand correctly, for given coordinates, you wish to bring 10 points in, for example, 3 groups. You are not certain how many coordinates there will be in each, but you wish to minimize some objective function based on Manhattan distance. Am I right? — Bruno Peixoto, Dec 01 '22 at 17:31
Yes, my bad in my example it would be 1 group of 12 points and 8 of 11 points. But yes you're right. — Antoine Descombes, Dec 01 '22 at 17:40

score 0 · Answer 1 · answered Dec 01 '22 at 18:54

In layman's terms, you wish to find k classification areas also known as clusters. In this case, I recommend you first read about clustering. After you acquire enough knowledge, you can advance on this related question, which generalizes this classification for a custom distance function.

How to allow a max Manhattan distance between all the points in a group

1 Answers1