An arborally satisfied point set is a 2D set of points such that, for any axis-aligned rectangle that can be formed using two points in the set as opposite corners, that rectangle contains or touches at least one other point. Here is an equivalent definition from Wikipedia:
A point set is said to be arborally satisfied if the following property holds: for any pair of points that do not both lie on the same horizontal or vertical line, there exists a third point which lies in the rectangle spanned by the first two points (either inside or on the boundary).
The following image illustrates how the rectangles are formed. This point set is NOT arborally satisfied because this rectangle needs to contain at least one more point.
In ASCII art, this point set can be represented as:
......
....O.
......
.O....
......
A slight modification can make this arborally satisfied:
......
....O.
......
.O..O.
......
Above, you can see that all rectangles (of which there is only one) contain at least three points.
Here is another example of a more complex point set that is arborally satisfied:
For any rectangle that can be drawn spanning two points, that rectangle contains at least one other point.
The Challenge
Given a rectangular grid of points (which I represent with O
) and empty space (which I represent with .
), output a truthy value if it is arborally satisfied, or a falsey value if it is not. This is code-golf.
Additional rules:
- You can choose to have the characters
O
and.
swapped out with any other pair of printable ASCII characters. Simply specify which character mapping your program uses. - The grid will always be rectangular. A trailing newline is allowable.
More Examples
Arborally satisfied:
.OOO.
OO...
.O.OO
.O..O
....O
..O..
OOOO.
...O.
.O.O.
...OO
O.O.
..O.
OOOO
.O.O
OO..
...
...
...
...
..O
...
O.....
O.O..O
.....O
OOO.OO
Not Arborally Satisfied:
..O..
O....
...O.
.O...
....O
..O..
O.OO.
...O.
.O.O.
...OO
O.....
..O...
.....O