I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

Even faster, you can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.

I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

Even faster, you can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2 for edges). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.

I don't know what is "optimal" in this case, but space partitioning methods can give you pretty fast solutions. For instance, you can put your rectangles in a k-d tree and then for each point descend the k-d tree until you reach a leaf, where you'll have either a single rectangle or a few rectangles to test against, depending on the details of your implementation.

You can also superimpose a fine grid, and have a list of rectangles that touch each cell (typically 1 or 2 for edges). To find out which rectangle a point belongs to, simply look up its cell and test against the corresponding rectangles.