Как организовать структуру данных для листа квадранта с точки зрения памяти?

Я не эксперт по JVM, но в прошлый раз, когда я проверял, объект Java имеет 8 байтов (64 бита) метаданных, которые, похоже, также требуют 64-битного выравнивания. На 32-битном Android-устройстве это может быть по-другому, но, судя по тому, что я обнаружил, вашим объектам Point потребуется 16 байтов, а не 6, например:

public class Point {
    // 8 byte metadata

    // 6 bytes of data.
    short x,y,v;

    // 2 bytes of padding for alignment of metadata.
}

... что-то в этом роде. Таким образом, это примерно в 2,67 раза больше использования памяти, чем оптимально необходимо для 3 16-битных shorts. Таким образом, одно из решений уменьшить объем памяти для точек менее чем наполовину, а также улучшить локальность ссылок — просто хранить все в одном или нескольких гигантских массивах short, например:

short xyz[num_points * 3];

Это потребовало бы очень, очень, очень близкого к оптимальному объему памяти (лишь малейшие накладные расходы, абсолютно тривиальные в данном случае, для хранения некоторых метаданных для массива, таких как его длина).

Тем не менее, если предположить, что Point составляет 16 байт, это объясняет только около половины вашего взрывного использования памяти (~ 23 мегабайта для точек). Другой, скорее всего, сами узлы вашего дерева квадрантов. Тем не менее, вы можете уменьшить это значение с 23 мегабайт до ~ 8,6 мегабайт, если это так, используя описанную выше технику.

Что касается остальной части используемой памяти, мое предложение номер один — избегать хранения отдельного ArrayList для каждого отдельного листового узла. Вы можете просто сохранить, скажем, индекс первой точки в большом списке массивов (только один для всего дерева) и, возможно, еще одно целое число для количества элементов, хранящихся в этом листе. Это пример псевдокода C-ish, но вы должны иметь возможность получить узлы своего дерева квадрантов, по крайней мере, примерно так:

struct QuadTreeNode
{
     // Stores AABB.
     float x1, x2, y1, y2;

     // Stores first child or -1 if empty.     
     int first_child;

     // Stores first element or -1 if this is not a leaf.
     int first_element;
};

struct QuadTree
{
     // Stores all the nodes in the quad tree. The 4
     // children of a node are stored contiguously.
     QuadTreeNode nodes[];

     // Stores all the elements in the quad tree. The
     // elements at the leaves are stored contiguously.
     Element elements[];
};

Это даже не совсем компактно, но достаточно компактно.