2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/138333Unit two-variable-per-inequality (UTVPI) constraints form one of the largest class of integer constraints which are polynomial time solvable (unless P=NP). There is considerable interest in their use for constraint solving, abstract interpretation, spatial databases, and theorem proving. In this paper we develop a new incremental algorithm for UTVPI constraint satisfaction and implication checking that requires O(m + n log n + p) time and O(n+m+p) space to incrementally check satisfiability of m UTVPI constraints on n variables and check implication of p UTVPI constraints.14 pages, 1 figureData Structures and AlgorithmsComputational GeometryLogic in Computer ScienceF.2.2; G.2.2text