Optimization and approximation on systems of geometric objects

NEW

Problem: Reconstructed statement: under the standard “scalable object” interpretation, a regular hexagon graph means an intersection graph of translates and positive homothetic copies of one fixed-orientation regular hexagon; “unit” means all scale factors are 1. The conjecture is:

If such graphs have polynomial-bit rational representations, then they have polynomial-bit rational representations that are polynomially separated, i.e. there is a polynomial $q$ such that every $n$-vertex represented graph has a representation with margin at least $2^{-q(n)}$ between the intersection and non-intersection inequalities for every pair.

The source phrase “other scalable objects” supports fixed orientation and homothets; arbitrary rotations are a different formalization depending on angle encoding.

Result: The conjecture is true in this formalization.

Let $K$ be a fixed regular hexagon, written in hexagonal coordinates as

$$K=\{(x,y): |x|\le 1,\ |y|\le 1,\ |y-x|\le 1\}.$$

Define

$$N(z)=\max\{|z_1|,|z_2|,|z_2-z_1|\}.$$

Then $K=\{z:N(z)\le1\}$, and for homothetic copies $H_v=c_v+r_vK$,

$$H_u\cap H_v\ne\varnothing \iff N(c_u-c_v)\le r_u+r_v,$$

because $K=-K$ and $r_uK+r_vK=(r_u+r_v)K$.

Assume a representation has rational parameters of bit length at most $L$. For each pair $u,v$, put

$$d_{uv}=N(c_u-c_v),\qquad s_{uv}=r_u+r_v$$

with $s_{uv}=2$ in the unit case. Since $d_{uv}$ is the maximum of three rational linear expressions with polynomially bounded bit length, every positive gap

$$|d_{uv}-s_{uv}|$$

is at least $2^{-O(L)}$, and all $d_{uv},s_{uv}$ are at most $2^{O(L)}$.

Let

$$\Delta=\min_{uv\notin E}(d_{uv}-s_{uv})>0$$

if nonedges exist. Choose rational

$$0<\eta\le \Delta/(4M), \qquad M=\max_{u,v}d_{uv},$$

with bit length $O(L)$; if there are no nonedges, take $\eta=1/2$. Replace every center by

$$c_v'=(1-\eta)c_v$$

and keep the same radii.

Then

$$d'_{uv}=N(c_u'-c_v')=(1-\eta)d_{uv}.$$

For every edge $uv$,

$$d'_{uv}\le (1-\eta)s_{uv}=s_{uv}-\eta s_{uv},$$

so the edge inequality is strict with margin at least $2^{-O(L)}$. For every nonedge,

$$d'_{uv}-s_{uv} =(d_{uv}-s_{uv})-\eta d_{uv} \ge \Delta-\Delta/4 \ge 3\Delta/4 \ge 2^{-O(L)}.$$

Thus the new representation is polynomially separated. Its coordinates still have polynomial bit length. Taking $L\le p(n)$ gives a polynomial $q(n)$.

This proves polynomial representation implies polynomial separation for both regular hexagons and unit regular hexagons, in the fixed-orientation scalable-object sense.

Citation: No existing resolution is used here. Conjecture source: E. J. van Leeuwen, Optimization and approximation on systems of geometric objects, PhD thesis, University of Amsterdam, 2009, §4.3.1.