Document Server@UHasselt >
Research >
Research publications >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/14863

Title:  Evaluating geometric queries using few arithmetic operations 
Authors:  Grimson, Rafael Heintz, Joos Kuijpers, Bart 
Issue Date:  2012 
Citation:  APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 23 (34), p. 179193 
Abstract:  Let P:=(P1,…,Ps) be a given family of nvariate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each 1 ≤ i ≤ s the polynomial P i can be evaluated using L arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family P is in a suitable sense generic. We construct a database D , supported by an algebraic computation tree, such that for each x∈[0,1]n the query for the signs of P 1(x), . . . , P s (x) can be answered using hdO(n2) comparisons and nL arithmetic operations between real numbers. The arithmeticgeometric tools developed for the construction of D are then employed to exhibit example classes of systems of n polynomial equations in n unknowns whose consistency may be checked using only few arithmetic operations, admitting, however, an exponential number of comparisons. 
URI:  http://hdl.handle.net/1942/14863 
DOI:  10.1007/s002000120172x 
ISI #:  000311495400005 
ISSN:  09381279 
Category:  A1 
Type:  Journal Contribution 
Validation:  ecoom, 2013

Appears in Collections:  Research publications

Files in This Item:

Description 
Size  Format 
 Journal version  938.93 kB  Adobe PDF 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
