Why is the first reduction from $S$ to $S'$ true? For example, when $(5,5,5,1),(1,1,1,5)\in S$, then there must exist a vector that dominates $(5,5,5,5)$. But $(5,5,5,5)$ cannot be built as the elementwise maximum from two of the twelve "two-coordinate" versions $(5,5,0,0),(5,0,5,0),\ldots,(0,0,1,5)$.

A) What is the well-known solution that uses Brouwer's fixed-point theorem? B) The discrete problem has definitely easy direct proofs, just by specializing the polygonal Jordan curve theorem. C) If the two paths don't cross, one can extend them to a crossing-free drawing of the (non-planar) complete bipartite graph $K_{3,3}$ by adding two new vertices and some curves outside the square. But I guess this does not count, as non-planarity of $K_{3,3}$ is based on Euler's polyhedral formula, and that in turn depends on the Jordan curve theorem, it seems.

@Sebastian, What do you mean, "any real matrix", for which matrix? Was my argument not short enough?

What precisely do you mean by "sparse"? A constant number of entries in each row and column? At most $m+n$ entries in total? Or why would the total number of entries not appear in the runtime? (And edit the problem rather than posting an answer) (And the upper bound $a,b<1$ seems to be irrelevant.)

Indeed, fullerenes are a good example. Almost all of the surface is a hexagonal lattice, and there you can simultaneously cut away vertices as long as their minimum distance is 2. Thus, you can cut away half of the vertices (almost; staying away from the pentagons).