Evaluating geometric queries using few arithmetic operations

DOI10.1007/s00200-012-0172-xzbMath1255.68061arXiv1111.0499OpenAlexW2962723050MaRDI QIDQ694567

Bart Kuijpers, Joos Heintz, Rafael Grimson

Publication date: 13 December 2012

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.0499

zbMATH Keywords

computational complexityconstraint databasequery evaluationconsistency of polynomial equation systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Database theory (68P15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• VPSPACE and a transfer theorem over the reals
• Point location in arrangements of hyperplanes
• Definability and fast quantifier elimination in algebraically closed fields
• Sur des hauteurs alternatives. I. (On alternative heights. I)
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Linear probing and graphs
• Sur des hauteurs alternatives. II (On alternative heights. II)
• On alternative heights. III
• Software engineering and complexity in effective algebraic geometry
• Efficient evaluation of specific queries in constraint databases
• Topological complexity of the range searching
• Finding a vector orthogonal to roughly half a collection of vectors
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Heights of Projective Varieties and Positive Green Forms
• Algorithms in real algebraic geometry