We also have the ability to discover the spender of a specific point (output) because we store the spender's height with the output when it is spent. This allows us to get the block at that height and search it for the spend, which remains a constant time query. However we don't currently expose a query for this.
Spender height exists primarily for chain validation purposes, because when there are reorgs we need to know if any output has become unspent, which is quickly obtained from the output's spender height field.
(edited)