Detecting common substructures between three-dimensional (3D) protein structures is a fundamental problem in structural bioinformatics and drug discovery. This issue can be formulated as the well-known geometric Largest Common Point-set (LCP) problem under the bottleneck distance. In this study, we focus on the order-dependent alignment variant. The fastest known exact algorithm for this variant has a time complexity of \(O(n^{32})\) , whereas the fastest approximation algorithm with a theoretical guarantee runs in \(O(n^8)\) time, where n is the size of the largest input structure. However, these algorithms suffer from impractical computational costs. Therefore, we propose two new approximation algorithms that improve efficiency and accuracy. The first algorithm optimizes an existing approach, achieving a reduced time complexity of \(O(n^7 \log n)\) , whereas the second algorithm provides even greater efficiency under specific conditions. We implement these algorithms and evaluate their performance using datasets from the Protein Data Bank (PDB). Experimental results demonstrate that our proposed methods outperform existing algorithms in both efficiency and accuracy, indicating their suitability for real-world applications. The implementation is publicly available at: https://github.com/masat03110/sLCP .