OPTICS relies on the nearest neighbor graph, and should be possible to perform with precomputed distances (maybe it does already, but I don't think it's tested), and with sparse feature spaces. It should perhaps also be possible to perform with sparse precomputed neighborhoods (e.g. as returned from radius_neighbors_graph(radius=max_bound)) but I've not double checked this.