I have a quadcopter robot that has a KINECT on it and i want to do 3D mapping with it.
With respect to the Arduino + Kinect, see my answer to Start making robots with Kinect (short version: not happening without something with more CPU power than a Raspberry Pi, which you then have to carry onboard with sufficient additional battery power).
The other obstacle in your case is that the specifications of the Kinect are not well-suited for any sort of aircraft. The effective range of the depth sensor is 1.2 - 3.5 meters. It won't be able to detect a wall right next to it or recognize it from a distance. Your copter would have to be able to react quickly enough to avoid obstacles in that 1.2 - 3.5 meter viewing range. Even then, it could get blindsided by something too close to ever be detected in the first place. You would have to add additional sensors for obstacle avoidance and only use the Kinect for mapping when you know it's safe to do so.
In answer to your q1 Kinect mapping quadcopter has been done: http://www.engadget.com/2010/12/06/kinect-used-as-a-quadrocopter-radar-video/
In answer to your q2 you can read from some of the online analyses of the project (http://aeroquad.com/archive/index.php/t-1503.html?s=eb7c86f8f916e82c4d8bb7476a68f608) the onboard computer was a 1.6GHz Intel Atom CPU, which is significantly more powerful than arduino.
I think what you are asking is on the edge of what is doable.
To specifically answer your questions;
You should probably use the ROS package RGBD Slam made for this exact process.
Yes, it uses SLAM.
No, an arduino is probably not sufficient, or appropriate. It will take a fairly powerful PC class computer to process 3D SLAM data, and that would be independent of any Autonomous processing - so it might actually need 2 full function PCs before it flies. Plus an arduino for flight control.
Being autonomous is an open concept. You have to write software that does something. SLAM will allow you to estimate where you are, and what your environment looks like, but you have to program the instructions to do anything within that environment. There is no general purpose "let's be autonomous" program.
The Kinect is part of a toy. It is reliable enough for experiments, you should at no time use a Kinect in any place where there is potential danger to life or property, such as on an unrestricted 'copter'.
The 'copter' will have to either have remote processing, which would involve some fairly high bandwidth transmission equipment, or be able to lift 2 decent size computers, plus a kinect in either case. The rule of thumb for 'copters' is 2 to 1 thrust to weight ratio, so you are looking at a fairly robust platform with eight motors (typical), costing several thousand dollars. I'm not sure a $10,000 cinestar would even be up to it, more and likely something custom beyond that.
Just as reference as to whether or not it is doable, I found a video showing it (a year ago, and we've gotten a little better since then).
This is absolutely not feasible. The Arduino cannot handle the data rate from the Kinect. It requires usb 2.0 (full speed) and a lot of power (full USB bus x2). Arduino would be swamped, especially given that the Kinect requires a dedicated and optimized library to interface. Such a library does not exist for the Arduino. The Kinect is not an appropriate sensor for controlling a copter, due to limited range, high power requirements, high weight, and huge processing requirements.
Yes, you will have to use SLAM algorithms, of course. What you describe is exactly the job SLAM addresses.
After reviewing the original post and the posted answers, I agree, the task is absolutely infeasible in real-time with Arduino. Don't even bother - Arduino is off by orders of magnitude.
Have you considered strapping a larger USB stick/flash drive on board, and then simply using the copter as a "sensor"? Fly the craft around, gather your 3D data, store it in flash, bring it home, and then aggregate/register/process your data offline. Very, very cool in my opinion.
