Identify arborally satisfied point sets

Question

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

Answer 1

Snails, 29 30 39 bytes

!{t\Oo\.+c\.,\O!{t\O{w!(.,~}2

It works by tracing out 2 sides of the rectangle, and then checking whether there is some square containing an O such that traveling in a straight line from the square in 2 of the cardinal directions would result in hitting a side of the rectangle.

Prints the maximum of 1 and the grid's area if the input is "arborally satisfied"; otherwise 0.

Answer 2

Oracle SQL 11.2, 364 344 bytes

WITH v AS(SELECT MOD(LEVEL-1,:w)x,FLOOR((LEVEL-1)/:w)y FROM DUAL WHERE'O'=SUBSTR(:g,LEVEL,1)CONNECT BY LEVEL<=LENGTH(:g))SELECT a.*,b.*FROM v a,v b WHERE b.x>a.x AND b.y>a.y MINUS SELECT a.*,b.*FROM v a,v b,v c WHERE((c.x IN(a.x,b.x)AND c.y>=a.y AND c.y<=b.y)OR(c.y IN(a.y,b.y)AND c.x>=a.x AND c.x<=b.x))AND(c.x,c.y)NOT IN((a.x,a.y),(b.x,b.y));

:g is the grid as a string
:w is the width of the grid

Returns no line as truthy, return the rectangles that do not match the criteria as falsy

Un-golfed

WITH v AS
(
  SELECT MOD(LEVEL-1,:w)x,FLOOR((LEVEL-1)/:w)y,SUBSTR(:g,LEVEL,1)p 
  FROM   DUAL 
  WHERE  'O'=SUBSTR(:g,LEVEL,1)
  CONNECT BY LEVEL<=LENGTH(:g)
)
SELECT a.*,b.*FROM v a,v b
WHERE b.x>a.x AND b.y>a.y
MINUS
SELECT a.*,b.*FROM v a,v b,v c
WHERE((c.x IN(a.x,b.x) AND c.y>=a.y AND c.y<=b.y) OR (c.y IN(a.y,b.y) AND c.x>=a.x AND c.x<=b.x))
  AND(c.x,c.y)NOT IN((a.x,a.y),(b.x,b.y));

The view v compute the coordinates of each O point.
The first part of the minus return all rectangles, the where clause insures that a point can not be paired with itself.
The second part search for a third point in each rectangle. That point needs to have one coordinate,x or y, equals to that coordinate for one of the two points defining the rectangle. The other coordinate of that third point needs to be in the range bounded by that coordinate for each of the points defining the rectangle.
The last part of the where clause insures that the third point is not one of the two points defining the rectangle.
If all the rectangles have at least a third point then the first part of the minus is equal to the second part and the query returns nothing.

Answer 3

MATL, 38 bytes

Ti2\2#fh!XJ"J@-XKtAZ)"@K-@/Eq|1>~As2>*

This uses a 2D char array as input, with rows separated by ;. So the first example is

['......';'....O.';'......';'.O..O.';'......']

The rest of the test cases in this format are as follows.

• 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']
  

Try it online! You can also verify all test cases at once.

Explanation

The code first gets the coordinates of characters O in the input. It then uses two nested loops. The outer loop picks each point P (2-tuple of its coordinates), compares with all points, and keeps points that differ from P in the two coordinates. Those are the points than can form a rectangle with P. Call them set R.

The inner loop picks each point T from R, and checks if the rectangle defined by P and T includes at least 3 points. To do that, it subtracts P from all points; that is, moves the origin of coordinates to P. A point is in the rectangle if each of its coordinates divided by the corresponding coordinate of T is in the closed interval [0, 1].

T          % push "true"
i          % take input 2D array
2\         % modulo 2: gives 1 for 'O', 0 for '.'
2#f        % row and column coordinates of ones. Gives two column arrays
h!         % concatenate horizontally. Transpose. Each point is a column
XJ         % copy to clipboard J
"          % for each column
  J        %   push all points
  @-       %   subtract current point (move to origin)
  XK       %   copy to clipboard K
  tA       %   logical index of points whose two coordinates are non-zero
  Z)       %   keep only those points. Each is a column
  "        %   for each column (point)
    @K-    %     push that point. Subtract all others
    @/     %     divide by current point
    Eq|1>~ %     true if in the interval [0,1]
    A      %     true if that happens for the two coordinates
    s      %     sum: find out how many points fulfill that
    2>     %     true if that number is at least 3
    *      %     multiply (logical and). (There's an initial true value at the bottom)
           %   end
           % end
           % implicit display

Answer 4

PHP, 1123 bytes, 851 bytes, 657 bytes

(newbie php)

<?php
$B=array_map("str_split",array_map("trim",file('F')));$a=[];$b=-1;foreach($B as $c=>$C){foreach($C as $d=>$Z){if($Z=='O'){$a[++$b][]=$c;$a[$b][]=$d;}}}$e=array();foreach($a as $f=>$l){foreach($a as $g=>$m){$h=$l[0];$i=$l[1];$j=$m[0];$k=$m[1];if($h!=$j&&$i!=$k&&!(in_array([$g,$f],$e,1)))$e[]=[$f,$g];}}$A=array();foreach($e as $E){$n=$E[0];$o=$E[1];$q=$a[$n][0];$s=$a[$n][1];$r=$a[$o][0];$t=$a[$o][1];$u=($q<$r)?$q:$r;$v=($s<$t)?$s:$t;$w=($q>$r)?$q:$r;$X=($s>$t)?$s:$t;$Y=0;foreach($a as $p){$x=$p[0];$y=$p[1];if($x>=$u&&$x<=$w&&$y>=$v&&$y<=$X){$Y=($x==$q&&$y==$s)||($x==$r&&$y==$t)?0:1;}if($Y==1)break;}if($Y==1)$A[]=1;}echo count($A)==count($e)?1:0;

explaination (commented code) :

<?php
//read the file
$lines=array_map("str_split",array_map("trim",file('F'))); // grid in file 'F'

//saving coords
$coords=[]; // new array
$iCoord=-1;
foreach($lines as $rowIndex=>$line) {
    foreach($line as $colIndex=>$value) {
        if ($value=='O'){
            $coords[++$iCoord][]=$rowIndex;//0 is x
            $coords[$iCoord][]=$colIndex;  //1 is y
        }
    }
}

/* for each point, draw as many rectangles as other points
 * without creating 'mirror' rectangles
 */ 
$rectangles=array();

foreach ($coords as $point1Index=>$point1) {
     //draw
     foreach ($coords as $point2Index=>$point2) {
            $point1X=$point1[0];
            $point1Y=$point1[1];
            $point2X=$point2[0];
            $point2Y=$point2[1];
            //if not on the same line or on the same column, ...
            if ($point1X!=$point2X &&   // same line
                $point1Y!=$point2Y &&   // same column
                !(in_array([$point2Index,$point1Index],$rectangles,true)) //... and if no 'mirror one' already
             ) $rectangles[]=[$point1Index,$point2Index]; //create a new rectangle
     }
 }
 
//now that we have rectangles and coords
//try and put a third point into each
$tests=array();
foreach ($rectangles as $rectangle) {
    $pointA=$rectangle[0];    // points of the rectangle
    $pointB=$rectangle[1];    // __________"____________
    $xA=$coords[$pointA][0];
    $yA=$coords[$pointA][1];
    $xB=$coords[$pointB][0];
    $yB=$coords[$pointB][1];
    $minX=($xA<$xB)?$xA:$xB;
    $minY=($yA<$yB)?$yA:$yB;
    $maxX=($xA>$xB)?$xA:$xB;
    $maxY=($yA>$yB)?$yA:$yB;

    $arborally=false;
    foreach ($coords as $point) {
        $x=$point[0];
        $y=$point[1];
        if ($x>=$minX &&
            $x<=$maxX &&
            $y>=$minY &&
            $y<=$maxY) {
                $arborally=($x==$xA&&$y==$yA) || ($x==$xB&&$y==$yB)?0:1; //same point (pointA or pointB)
        }     
        if ($arborally==true) break;//1 found, check next rectangle
    }
    if ($arborally==true) $tests[]=1;//array of successes
    
}

echo count($tests)==count($rectangles)?1:0; //if as many successes than rectangles...

?>

Answer 5

C, 289 bytes

a[99][99],x,X,y,Y,z,Z,i,c;main(k){for(;x=getchar(),x+1;x-10||(y=0,i++))a[y++][i]=x;for(;X<i;X++)for(x=0;a[x][X]-10;x++)for(Y=X+1;Y<i;Y++)for(y=0;a[y][Y]-10;y++)if(x-y&&!(a[x][X]-79||a[y][Y]-79)){c=0;for(Z=X;Z<=Y;Z++)for(z=x<y?x:y;z<=(x>y?x:y);)a[z++][Z]-79||c++;c-2||(k=0);}putchar(k+48);}

Requires trailing newline, which is permitted (without the newline, the code would be two bytes larger). Outputs 0 (not arborally satisfied) or 1 (arborally satisfied).