This is the problem I am dealing with:

Given a set P of n points in general position, let a graph G be defined as follows:

The vertex set is P. Two vertices, a and b, are joined by an edge provided there exists an axis parallel square S with a and b on the boundary and no other point of P in the interior of S.

I need to prove or disprove that G is a near-triangulation where every face except the outerface is a triangle and the outerface is a cycle.

Thanks in advance

  • $\begingroup$ Could you define exactly what a near triangulation is? $\endgroup$ – Tassle Dec 9 '19 at 22:07
  • $\begingroup$ By triangulating any polygon, all the faces except the outer face becomes a triangle. This is called Near-Triangulation. Now suppose the polygon itself is a triangle, then by triangulation, all the faces including the outer face is a triangle. This is perfect triangulation. $\endgroup$ – AlgorithmUser785 Dec 10 '19 at 1:36
  • $\begingroup$ I think a picture will worth a thousand words $\endgroup$ – HEKTO Dec 10 '19 at 4:38

An easy contradicting example is three points forming an obtuse triangle. Note that any Axis-parallel square containing $A$ and $B$ on its boundaries, contains $C$ in its interior and hence, the outer face is not bounded by a cycle since $AB$ is not an edge in the graph.

Obtuse triangle

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.