Localizer: a solver for the point realizability problem

The 'realizability problem' is a well-known hard problem in computational geometry, consisting of receiving a set of constraints on the relative positions of points in the plane and determining whether there exists a configuration of points in general position that satisfies all the constraints. Localizer is a local-search solver for this problem. In particular, Localizer receives a set of constraints of the form A_(i, j, k), or B_(i, j, k), where A_(i, j, k) means that point i is above the directed line from point j to point k, and B_(i, j, k) means that point i is below the directed line from point j to point k. Equivalently, A_(i, j, k) is equivalent to Knuth's CC relation (see https://link.springer.com/book/10.1007/3-540-55611-7). Formally, A_(i, j, k) imposes a constraint on points $p_i = (x_i, y_i)$, $p_j = (x_j, y_j)$, and $p_k = (x_k, y_k)$ equivalent to:

$$\text{det} \begin{pmatrix} x_i & x_j & x_k \\\ y_i & y_j & y_k \\ 1 & 1 & 1 \end{pmatrix} > 0,$$

and B_(i, j, k) states that the determinant is strictly less than zero.

Quick Start

# Build the executable
make -C src

# Run with an orientation file
src/localizer path/to/orientation_file.or -o solution.txt

# Plot the solution
python3 scripts/plotter.py --sol solution.txt

You can try with the examples/trivial_example.or file! For a much cooler example, go to the Symmetry section at the end of this README.

Usage

localizer <orientation_file> [-i <sub_iterations>] [-o <output_file>] [-s <seed>] [-r <reset_interval>] [-t <threads>] [-f <fixed_points_file>] [-c <symmetry_file>]

Input Format

The orientation file must follow these rules:

1. Each line contains an "orientation" in the format <O>(<a>, <b>, <c>).
2. <O> must be either "A" (above), "B" (below), or "C" (collinear). "C" is not currently well supported, as collinearities are harder to deal with. This is part of the future work of this repo.
3. The parameters <a>, <b>, <c> are positive integers where 1 <= a < b < c.

For example, A(2, 4, 7) means point 2 is above the directed line from point 4 to point 7.

Command Line Options

Option	Description	Default Value
-i	Sub-iterations	10
-o	Output file path	output.txt
-s	Random seed	42
-r	Reset interval	30000
-t	Number of threads	1
-f	Fixed points file (see below)	N/A
-c	Symmetry file (see below)	N/A

The number of sub-iterations indicates how many times in a row a chosen point will be moved. The reset interval indicates how many iterations without an improvement will be done before resetting the current solution.

Visualization

Plot a solution generated by the localizer:

python3 scripts/plotter.py --sol <output_file>

This creates <output_file>.png with a visualization of the point set.

Validation

Validate a solution against constraints:

python3 scripts/validator.py -c <constraint_file> -p <point_file>

Running Benchmarks

Execute the benchmark suite:

python3 scripts/eval_benchmarks.py -e <path to localizer executable> [-b] [-L <lower_N>] [-R <upper_N>] [-n <iterations>] [-t <timeout>] [-o <output_file>]

The -b option builds the benchmark examples, which you can avoid if you already have run this command before, also allowing to compare against the same examples. The -L and -R options specify the range of values for the number of points N in the benchmarks. The -n option specifies the number of iterations for each benchmark, and the -t option specifies the timeout for each iteration. For example, to test with N = 10...20 and 10 random cases for each N, run:

python3 scripts/eval_benchmarks.py -e src/localizer -b -L 10 -R 20 -n 10

Fixing points

Another feature of Localizer is the ability to fix the coordinates of some points in the solution. This is done by providing a file with the coordinates of the points to be fixed. The format of the file is as follows:

<index1>:<x1>,<y1>
...
<indexN>:<xN>,<yN>

Where <index> is the index of the point to be fixed (starting from 1), and <x> and <y> are the coordinates of the point. For example (corresponding to the file examples/4fixed_pts.txt):

1:0.0,-30.0
2:30.0,0.0
3:0.0,30.0
4:-30.0,0.0

Try for instance

src/localizer examples/16-6-4fold-orientations/N_16_sol_924_208_0_2.or -f examples/4fixed_pts.txt

Symmetry

We can also provide a file specifying a desired rotational symmetry of the solution. Naturally, this symmetry must be compatible with the orientation constraints. The format of the file is as follows:

<indices of orbit1>
...
<indices of orbitN>

where each line contains the indices of the points in the same orbit. For example (corresponding to the file examples/4fold_symmetry_16.txt):

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

enforces a 4-fold symmetry on those 16 points. Orbits can have different lengths. Concretely, these orbits are enforcing that the coordinates of the points are $$2\pi/k$$ rotated with respect to the previous point in the orbit, where $k$ is the length of the orbit.

For a nice complete example, you can

src/localizer examples/16-6-4fold-orientations/N_16_sol_924_208_0_2.or -c examples/4fold_symmetry_16.txt -f examples/4fixed_pts.txt -o symmetric_solution16.txt
python3 scripts/plotter.py --sol symmetric_solution16.txt

Disclaimers

Localizer has been tested in MacOS (Sonoma 14.4.1) and Ubuntu 24.04.1. Currently, the hyperparameter MAX_POINTS in src/utils.c determines the maximum number of points supported, and it's set 81. This helps with static memory allocation. For trying it over larger pointsets simply increase the value of MAX_POINTS. Conversely, performance might be ever so slightly faster by reducing it to just above the number of points you want to try it on.