CG models of computation?

[Joachim Gudmundsson]

Dear Colleagues, I have a question about which models 
of computation that are accepted in the computational 
geometry community. 

In many of the papers I have co-authored we have 
strived to use the algebraic decision tree model of 
computation (sometimes extended with indirect 
addressing), but sometimes also using the real RAM.

Recently, I read an excellent paper where the authors 
add the power of the floor function to the standard 
model of computation. The running time of their 
algorithm is almost linear and beats the lower bound 
in the comparison model. 

Somewhat puzzled and skeptical I asked my colleagues 
about their opinion on this topic, only to find out that 
this model was, according to my colleagues, unofficially 
accepted. One of my colleagues even claimed that it was 
so widely accepted that it is not even necessary to 
explicitly point out in a paper if the floor function 
is used or not. Amazed about this information I went 
back to my office and looked at a paper I'm currently 
working on. Adding the floor function would trivially 
improve the running time of the algorithm from 
O((m+n) log n) to O(m+n log n), maybe even more. My 
question is, what is "unofficially" allowed? One could 
claim that the use of floor function should be accepted 
since it is used in practice and very fast. How about 
bit manipulation? But then we should measure the 
complexity in the number of input bits, right? 

Anyway, I would be very happy if anyone could help remove 
my obvious ignorance on this topic.

Sincerely,
Joachim Gudmundsson


-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.