Are there any algorithms that allow quick/efficient lookup of hexes based on location on a large subdivided hex/pentagon tiled icosphere?

Question

So, I have a subdivided icosahedron sphere (icosphere), and I am looping through its vertices and creating a logical tile-map of hexagons at the location of every vertex in the array. Basically, now I need to start detecting input on the tile-map, and looping through 10k tiles and doing a bounds check every time the user hovers a mouse over or clicks the sphere is way too computationally expensive.

I need a way to quickly and efficiently get the tile the user clicks/hovers over.

My current idea would be to create a 2D array of tiles (lat/lon), convert the tile's position to lat/lon values, and store the tile at tiles[lat][lon].

The issue with this solution is, latitude and longitude are stored as float values - in this case, they are (in terms of distance) "the sphere's radius" away from the sphere's center-point. If I do this, I have to scale the sphere up dramatically, and it's pretty likely that there are going to be many "un-used" slots in the array that contain null values. This is pretty messy. If we did this, we'd also have to find some way to ensure that the lat/lon value approximately maps directly onto the tile's x/y coord in the array of tiles (i.e. we could just do tiles[(int)lat][(int)lon] to get a tile, but again, this will create an array with many empty slots (which, to my understanding, translates to a lot of wasted memory, as an added negative).

I could also store tiles in a dictionary of dictionaries - with the outer dictionary being ArrayMap<Float, ArrayMap<Float, IcoSphereTile>>. The issue here is, I'm not quite sure how performant that could really be - we're talking lookups of arrays with hundreds or thousands of tiles in them on a pretty regular basis.

If I make sure tiles are ordered, a tweaked implementation of a binary search algorithm might also be viable.

What are your thoughts? How would you go about designing a quick/efficient coordinate system?

Edit: Somebody asked me to post my code:

public class Hexasphere
{
    private Vector3 center;
    private Array<Point> points;
    private Array<Triangle> faces;
    private Model model;
    private float radius = 3f;
    private int subdivisions;

    //ArrayMap<Float, ArrayMap<Float, IcoSphereTile>> latLon;
    Float2ObjectArrayMap<Float2ObjectArrayMap<IcoSphereTile>> latLon;

    public Hexasphere(int subdivisions)
    {
        points = new Array<Point>(true, 12);
        faces = new Array<Triangle>(true, 20);
        this.latLon = new Float2ObjectArrayMap<Float2ObjectArrayMap<IcoSphereTile>>(); //new ArrayMap<Float, ArrayMap<Float, IcoSphereTile>>();
        this.center = new Vector3(0f, 0f, 0f);
        this.subdivisions = subdivisions;

        createIcosahedron();

        subdivide(this.subdivisions);

        tileIcosphere();

        buildMesh();
    }

    //Based on the following articles:
    //      1. http://blog.andreaskahler.com/2009/06/creating-icosphere-mesh-in-code.html
    //      2. https://www.classes.cs.uchicago.edu/archive/2003/fall/23700/docs/handout-04.pdf
    private void createIcosahedron()
    {
        float tao = 1.61803399f; //(float)(1.0f + Math.sqrt(5.0f)) / 2.0f;

        Color[] colors = new Color[] {
            Color.GREEN,
            Color.RED,
            Color.BLUE,
            Color.BROWN,
            Color.CHARTREUSE,
            Color.CORAL,
            Color.CYAN,
            Color.DARK_GRAY,
            Color.FIREBRICK,
            Color.FOREST,
            Color.GOLD,
            Color.LIME,
            Color.LIGHT_GRAY,
            Color.OLIVE,
            Color.SKY,
            Color.SALMON
        };

        Point[] pnts = new Point[]
        {
            new Point(radius, tao * radius, 0),
            new Point(-radius, tao * radius, 0),
            new Point(radius,-tao * radius,0),
            new Point(-radius,-tao * radius,0),
            new Point(0, radius,tao * radius),
            new Point(0,-radius,tao * radius),
            new Point(0, radius,-tao * radius),
            new Point(0,-radius,-tao * radius),
            new Point(tao * radius,0, radius),
            new Point(-tao * radius,0, radius),
            new Point(tao * radius,0,-radius),
            new Point(-tao * radius,0,-radius)
        };

        Triangle[] fces = new Triangle[]
        {
            new Triangle(this, 0, 1, 4, false),
            new Triangle(this, 1, 9, 4, false),
            new Triangle(this, 4, 9, 5, false),
            new Triangle(this, 5, 9, 3, false),
            new Triangle(this, 2, 3, 7, false),
            new Triangle(this, 3, 2, 5, false),
            new Triangle(this, 7, 10, 2, false),
            new Triangle(this, 0, 8, 10, false),
            new Triangle(this, 0, 4, 8, false),
            new Triangle(this, 8, 2, 10, false),
            new Triangle(this, 8, 4, 5, false),
            new Triangle(this, 8, 5, 2, false),
            new Triangle(this, 1, 0, 6, false),
            new Triangle(this, 11, 1, 6, false),
            new Triangle(this, 3, 9, 11, false),
            new Triangle(this, 6, 10, 7, false),
            new Triangle(this, 3, 11, 7, false),
            new Triangle(this, 11, 6, 7, false),
            new Triangle(this, 6, 0, 10, false),
            new Triangle(this, 9, 1, 11, false)
        };

        for(int i = 0; i < pnts.length; i++)
        {
            Point p = pnts[i];
            Color c = colors[i];
            p.setColor(c);
            points.add(p);
        }

        for(Triangle f : fces)
        {
            faces.add(f);
        }
    }

    // Not implemented yet...
    public void tileIcosphere()
    {
        for(int i = 0; i < points.size; i++)
        {
            Point p = points.get(i);
            float polarAngle = (float)Math.acos(p.getPosition().z / getRadius());
            float azimuthAngle = (float)Math.atan2(p.getPosition().y, p.getPosition().x);
            float lat = 90f - polarAngle;
            float lon = azimuthAngle;
            //IcoSphereTile(this, points.get(i), IcoSphereTile.TileType.GRASS);
        }
    }

    public void subdivide(int times)
    {
        // We are caching the old array of triangles because
        // removeFace (called in the Triangle.subdivide() method) mutates our main array of triangles ("faces").
        // If we just use "faces," then faces are removed and added during the loop,
        // leading to infinite regression
        // (size is always increasing faster than i is incrementing - by a factor
        // of 4 new triangles per triangle iterated through)
        // This is super inefficient for larger meshes/more subdivisions.
        // We should be caching only the new triangles we create, and adding them to the main faces
        for(int i = 0; i < times; i++)
        {
            var newFaces = new Array<Triangle>(faces);
            for(int j = 0; j < newFaces.size; j++)
            {
                newFaces.get(j).subdivide();
            }
            //newFaces = new Array<Triangle>(faces);
        }
    }

    public void addRawTriangle(Point p1, Point p2, Point p3)
    {
        short p1Idx, p2Idx, p3Idx;
        p1Idx = (short)addPointIfDoesNotExist(p1);
        p2Idx = (short)addPointIfDoesNotExist(p2);
        p3Idx = (short)addPointIfDoesNotExist(p3);

        Triangle tri = new Triangle(this, p1Idx, p2Idx, p3Idx);
        faces.add(tri);
        getPointAt(tri.getIdx1()).setIndex(tri.getIdx1());
        getPointAt(tri.getIdx2()).setIndex(tri.getIdx2());
        getPointAt(tri.getIdx3()).setIndex(tri.getIdx3());
    }

    //This doesn't remove vertices, it just removes the specific triangle/collection of indices that form the triangle.
    public void removeTriangle(Triangle tri)
    {
        this.faces.removeValue(tri, true);
    }

    public void buildMesh()
    {
        ModelBuilder modelBuilder = new ModelBuilder();
        MeshBuilder b = new MeshBuilder();

        b.begin(VertexAttributes.Usage.Position | VertexAttributes.Usage.Normal |VertexAttributes.Usage.ColorUnpacked);
        for(int i = 0; i < points.size; i++)
        {
            Point point = points.get(i);

            b.vertex(
                point.getPosition(),
                point.getPosition(),
                point.getColor(),
                new Vector2(1, 1));
        }
        for(int i = 0; i < faces.size; i++)
        {
            b.index(faces.get(i).getIdx1());
            b.index(faces.get(i).getIdx2());
            b.index(faces.get(i).getIdx3());
        }
        Mesh mesh = b.end();
        modelBuilder.begin();
        modelBuilder.part("world", mesh,  GL20.GL_TRIANGLES, new Material(ColorAttribute.createDiffuse(Color.WHITE)));
        this.model = modelBuilder.end();
    }

    //Thank the Gods for this brave soul: https://gamedev.stackexchange.com/a/212473/60136
    public ModelInstance instance()
    {
        return new ModelInstance(model);
    }

    public Point getPointAt(int index)
    {
        return points.get(index);
    }

    // Adds the point and returns its index if it does not exist.
    // Returns the index of the point if it does exist.
    public int addPointIfDoesNotExist(Point point)
    {
        int retval = -1;
        for(int i = 0; i < points.size; i++)
        {
            Point other = points.get(i);
            if(other == point || other.equals(point))
            {
                retval = i;
                //Gdx.app.debug("Hexasphere", "Point " + point.getPosition() + " exists! Returning " + retval);
                break;
            }
        }
        if(retval == -1)
        {
            points.add(point);
            retval = points.size - 1;
            //Gdx.app.debug("Hexasphere", "Point " + point.getPosition() + " does not exist! Returning " + retval);
        }

        return retval;
    }

    public float getRadius()
    {
        return this.radius;
    }

    public Vector3 getCenter()
    {
        return this.center;
    }

    public void debugMesh(boolean verts, boolean faces)
    {
        String vertsDebug = "\n";
        String facesDebug = "\n";

        if(verts)
            for(Point p : points)
                vertsDebug += "point [" + p.getPosition().toString() + "]\n";
        vertsDebug += "Vert Count: " + points.size;
        if(faces)
            for(Triangle f : this.faces)
                facesDebug += "face [" + f.toString() + "]\n";
        facesDebug += "Face Count: " + this.faces.size;
        Gdx.app.log("Vertices", vertsDebug);
        Gdx.app.log("Faces", facesDebug);
    }
}

And this is my Triangle class:

public class Triangle
{
    private Hexasphere hexasphere;
    private int index1, index2, index3;

    public Triangle(Hexasphere hexasphere, int idx1, int idx2, int idx3)
    {
        this(hexasphere, idx1, idx2, idx3, false);
    }

    public Triangle(Hexasphere hexasphere, int idx1, int idx2, int idx3, boolean trackFaceInPoints)
    {
        this.hexasphere = hexasphere;
        this.index1 = idx1;
        this.index2 = idx2;
        this.index3 = idx3;
    }

    public void subdivide()
    {
        //The three initial points.
        Point p1 = hexasphere.getPointAt(index1);
        Point p2 = hexasphere.getPointAt(index2);
        Point p3 = hexasphere.getPointAt(index3);
        Point[] oldPoints = new Point[] {p1, p2, p3};
        projectToSphere(p1.getPosition(), hexasphere.getCenter());
        projectToSphere(p2.getPosition(), hexasphere.getCenter());
        projectToSphere(p3.getPosition(), hexasphere.getCenter());

        //The three new points.
        Point p4 = getMidPoint(hexasphere.getPointAt(index1), hexasphere.getPointAt(index2));
        Point p5 = getMidPoint(hexasphere.getPointAt(index1), hexasphere.getPointAt(index3));
        Point p6 = getMidPoint(hexasphere.getPointAt(index2), hexasphere.getPointAt(index3));
        projectToSphere(p4.getPosition(), hexasphere.getCenter());
        projectToSphere(p5.getPosition(), hexasphere.getCenter());
        projectToSphere(p6.getPosition(), hexasphere.getCenter());

        Point[] newPoints = new Point[] {p4, p5, p6};
        for(int i = 0; i < newPoints.length; i++)
            newPoints[i].setColor(oldPoints[i].getColor().cpy());

        hexasphere.addRawTriangle(p6, p3, p5);
        hexasphere.addRawTriangle(p5, p1, p4);
        hexasphere.addRawTriangle(p4, p6, p5);
        hexasphere.addRawTriangle(p6, p4, p2);

        hexasphere.removeTriangle(this);
    }

    private Point getMidPoint(Point p1, Point p2)
    {
        Vector3 p1Pos = p1.getPosition();
        Vector3 p2Pos = p2.getPosition();

        float x1 = p1Pos.x, y1 = p1Pos.y, z1 = p1Pos.z;
        float x2 = p2Pos.x, y2 = p2Pos.y, z2 = p2Pos.z;
        return new Point((x1 + x2)/2f, (y1 + y2)/2f, (z1 + z2) / 2f);
    }

    private void projectToSphere(Vector3 objVector, Vector3 centerVector)
    {
        //Magnitude = sqrt((x₁ - x₀)² + (y₁ - y₀)² + (z₁ - z₀)²)
        float xDistance = (float)(Math.pow((objVector.x-centerVector.x), 2d));
        float yDistance = (float)(Math.pow((objVector.y-centerVector.y), 2d));
        float zDistance = (float)(Math.pow((objVector.z-centerVector.z), 2d));
        float magnitude = (float)Math.sqrt((xDistance + yDistance + zDistance));
        objVector.x /= magnitude / hexasphere.getRadius();
        objVector.y /= magnitude / hexasphere.getRadius();
        objVector.z /= magnitude / hexasphere.getRadius();
    }

    public Point getPoint1()
    {
        return hexasphere.getPointAt(index1);
    }

    public Point getPoint2()
    {
        return hexasphere.getPointAt(index2);
    }

    public Point getPoint3()
    {
        return hexasphere.getPointAt(index3);
    }

    public short getIdx1()
    {
        return (short)index1;
    }

    public short getIdx2()
    {
        return (short)index2;
    }

    public short getIdx3()
    {
        return (short)index3;
    }

    @Override
    public String toString()
    {
        return "{" + getIdx1() + ", " + getIdx2() + ", " + getIdx3() + "}";
    }
}