Are there any proven data structures for point location in tetrahedron meshes where the tetrahedra are all disjoint but are "touching" each other? I.e. most faces are faces of exactly two tetrahedra.

By locationI mean that I want to find out in which of the tetrahedrons a given point is located, or if it is not located in any.

So far, I have tried:

1. A simple KD-Tree. This was way too slow for my needs, as the average tree depth was very high and I still had a lot of individual tetrahedrons to test in each leaf.
2. A grid which contained all the intersecting tetrahedra for each cell. This seems to work a lot better, but was still not fast enough. First, the grid contained a lot of empty cells because my overall mesh is not very "boxy". Second, most cells that actually did contain tetrahedra, did contain a lot of them (10+). I suppose this is because a lot of tetrahedra share every vertex, and as soon as a vertex is in a cell, all its adjacent tetrahedra are too.

Some further information on the input data: The mesh is usually not convex and may have holes or inclusions. Though the last two are somewhat unlikely, i have to deal with them, which makes "walking" impossible without (expensive and complicated?) preprocessing.