# Finding four states each of six pairs of which have common boundary using PostGIS?

A Mathematics SE question on common boundary points of connected sets inspires this one.

Construing the word "state" broadly (so that, for example, each province or territory of Canada is a "state") is there any place on earth where, among four states, each a contiguous region, every one of the six pairs among them share a common boundary that is not just a point?

(As a matter of geometry, this can happen with four regions but not with five or more.)

A map of the United States shows Colorado, New Mexico, Arizona, and Utah meeting at an isolated point, and in Canada the provinces of Manitoba and Saskatchewan and the Northwest Territories and the territory of Nunavut similarly share an isolated point. I don't know any others of that sort, but I suspect some exist.

(If the four states are A, B, C, D, then the six pairs are AB, AC, AD, BC, BD, CD.)

The following diagram shows a simplified topology.

The shared boundaries AB, AC, AD, BC, BD and CD should all be lines.

• While GIS could be used to answer this question, I don't see how it's GIS-centric enough for GIS SE. Oct 11, 2017 at 16:42
• Besides, GIS software, can it be answered without tediously searching all maps covering the earth or else relying on sources that have contributions from someone who did that? Oct 11, 2017 at 16:51
• It would help if OP wants to clarify which GIS tools they want to use. I suspect it might be possible with any spatial database with de-9im support. Oct 11, 2017 at 17:14
• Could you draw a diagram of how four states can share more than a point, eg a line segment? I can't see how this is possible as a planar partition. Oct 11, 2017 at 17:23
• For CO, NM, OK, TX, you can get 5 of the 6. Oct 11, 2017 at 18:08

Here's an attempt with postgis. i've used data imported from natural earth data, admin level 1, 1:10m scale.

This will take a long time as it's a 4-way cartesian join with st_relate().

The magic number "FF2F11212" should match when two polygons' intersections are a line, but not when they join at a point. This uses something called DE-9IM. I use a cheatsheet i put together a while back to work out the value.

There are possibly mistakes in here, and potenial optimisations.

From my understanding, the question being

• are there any sets of 4 polygons which intersect
• their combinatorial intersections are ALL lines

I found 109 cases from Natural Earth data. Here's one example (I think...)

When this query returns, if there are no rows then the answer is false, otherwise it should list all groups matching the requirement.

``````select
s_a.gid,
s_b.gid,
s_c.gid,
s_d.gid,
st_asewkt(s_a.geom),
st_asewkt(s_b.geom),
st_asewkt(s_c.geom),
st_asewkt(s_d.geom)
from
(select gid, geom from states) as s_a,
(select gid, geom from states) as s_b,
(select gid, geom from states) as s_c,
(select gid, geom from states) as s_d
where
-- this is a way 4 cartesian join so we need to avoid unneccessary checks!
s_a.gid < s_b.gid and
s_b.gid < s_c.gid and
s_c.gid < s_d.gid and
s_a.gid != s_b.gid and
s_a.gid != s_c.gid and
s_a.gid != s_d.gid and
s_b.gid != s_c.gid and
s_b.gid != s_d.gid and
s_c.gid != s_d.gid and
-- check combinations intersect
st_intersects(s_a.geom, s_b.geom) and
st_intersects(s_a.geom, s_c.geom) and
st_intersects(s_a.geom, s_d.geom) and
st_intersects(s_b.geom, s_c.geom) and
st_intersects(s_b.geom, s_d.geom) and
st_intersects(s_c.geom, s_d.geom) and
-- check each of 6 intersections is a line
st_relate(s_a.geom, s_b.geom) = 'FF2F11212' and
st_relate(s_a.geom, s_c.geom) = 'FF2F11212' and
st_relate(s_a.geom, s_d.geom) = 'FF2F11212' and
st_relate(s_b.geom, s_c.geom) = 'FF2F11212' and
st_relate(s_b.geom, s_d.geom) = 'FF2F11212' and
st_relate(s_c.geom, s_d.geom) = 'FF2F11212'
group by
s_a.gid,
s_b.gid,
s_c.gid,
s_d.gid,
s_a.geom,
s_b.geom,
s_c.geom,
s_d.geom
order by
s_a.gid asc,
s_b.gid asc,
s_c.gid asc,
s_d.gid asc
;
``````