<p>Let $F = (f_1, \ldots, f_n)$ be a sequence of multivariate polynomials $f_i : \mathbb{R}^d \to \mathbb{R}$, and $g : \{0,1\}^n \to \{0,1\}$ a boolean function.  Say the composition
$$h(x)=g(f_1(x)&gt;0,\ldots,f_n(x)&gt;0)$$
answers some useful geometric question (e.g., is the intersection of two circles inside a third?).  Let $\deg(F) = \max_i \deg(f_i)$ be the maximum degree of any of the polynomials.</p>

<p><em>Question</em>: Is there an algorithm to check whether $\deg(F)$ can be reduced without changing $h(x)$?  Are there practical implementations of such (perhaps in Mathematica or Sage)?</p>

<p>I believe this is essentially a question of polynomial irreducibility, and the answer may be as simple as checking whether the highest degree $f_i$s factor.  However, since the answer may be simply be "yes, it's minimal", I want to be sure before I publish such a claim.</p>

CC BY-SA 3.0
2013-05-19T04:08:11.430Z
This should have been studied before. See maybe:  https://en.wikipedia.org/wiki/Real_algebraic_geometry Also, the book "Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algorithms in real algebraic geometry" might be useful.
Sariel Har-Peled
CC BY-SA 3.0
2013-05-19T07:42:02.763Z
Wonderful, that looks like a terrific book!  I've been looking around for a good reference on algorithm semi-algebraic geometry and hadn't found one yet.  On the other hand, I think there's a good chance that algebraic geometry over $\mathbb{C}$ may be enough for this question, at least for a good number of predicates.  For example, after working through various predicates the semi- part seems to arise as lower degree structure, such as for a sign check before squaring both sides of an inequality, and may effect the maximum degree only weakly.
Geoffrey Irving
CC BY-SA 3.0
2013-05-21T23:17:32.140Z
I suspect this is also well studied - but I do not know...
Sariel Har-Peled
<cg.comp-geom><polynomials>
Verifying the minimum degree of a geometric predicate
Geoffrey Irving
# Verifying the minimum degree of a geometric predicate

(Asked by: username_0 on 2013-05-17)

Let $F = (f\_1, \ldots, f\_n)$ be a sequence of multivariate polynomials $f\_i : \mathbb{R}^d \to \mathbb{R}$, and $g : \{0,1\}^n \to \{0,1\}$ a boolean function. Say the composition
$$h(x)=g(f\_1(x)>0,\ldots,f\_n(x)>0)$$
answers some useful geometric question (e.g., is the intersection of two circles inside a third?). Let $\deg(F) = \max\_i \deg(f\_i)$ be the maximum degree of any of the polynomials.

*Question*: Is there an algorithm to check whether $\deg(F)$ can be reduced without changing $h(x)$? Are there practical implementations of such (perhaps in Mathematica or Sage)?

I believe this is essentially a question of polynomial irreducibility, and the answer may be as simple as checking whether the highest degree $f\_i$s factor. However, since the answer may be simply be "yes, it's minimal", I want to be sure before I publish such a claim.

**Tags:** cg.comp-geom, polynomials
> **Comments:**
> **username_1**: This should have been studied before. See maybe:  https://en.wikipedia.org/wiki/Real_algebraic_geometry Also, the book "Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algorithms in real algebraic geometry" might be useful.  
> **username_0**: Wonderful, that looks like a terrific book!  I've been looking around for a good reference on algorithm semi-algebraic geometry and hadn't found one yet.  On the other hand, I think there's a good chance that algebraic geometry over $\mathbb{C}$ may be enough for this question, at least for a good number of predicates.  For example, after working through various predicates the semi- part seems to arise as lower degree structure, such as for a sign check before squaring both sides of an inequality, and may effect the maximum degree only weakly.  
> **username_1**: I suspect this is also well studied - but I do not know...  

---

## 0 answers

