Phương pháp cụm hóa phân vùng là mong muốn vì nó giảm thiểu khoảng cách giữa các tập hợp và tâm cụm của chúng. Nếu chọn phương pháp k-means, tâm cụm có thể không khả dụng do sự tồn tại của chướng ngại vật.
Ví dụ, cụm có thể ra ở giữa hồ nước. Nói cách khác, phương pháp k-medoids chọn một đối tượng bên trong cụm làm tâm và do đó đảm bảo vấn đề không xuất hiện.
Mỗi khi một medoid mới được chọn, khoảng cách giữa mỗi đối tượng và tâm cụm mới chọn phải được tính lại. Vì có thể có chướng ngại vật giữa hai đối tượng, khoảng cách giữa hai đối tượng có thể được suy ra bằng tính toán hình học (ví dụ liên quan đến tam giác).
Chi phí tính toán có thể cao nếu số lượng lớn đối tượng và chướng ngại vật được chứa. Bài toán cụm hóa với chướng ngại vật có thể được định nghĩa bằng mô tả đồ họa. Trước hết, điểm p nhìn thấy được từ điểm q khác trong vùng R, nếu đường thẳng nối p và q không cắt chướng ngại vật nào.
Đồ thị khả thi (visibility graph) là đồ thị VG = (V, E), trong đó mỗi đỉnh của chướng ngại vật có nút tương đương trong V và hai nút v₁ và v₂ trong V được nối bởi cạnh trong E nếu và chỉ nếu đỉnh tương đương mà chúng định nghĩa nhìn thấy được lẫn nhau.
Cho VG' = (V', E') là đồ thị khả thi tạo từ VG bằng cách thêm hai điểm bổ sung p và q vào V'. E' bao gồm cạnh nối hai điểm trong V₀ nếu hai điểm nhìn thấy được lẫn nhau.
Để giảm chi phí tính toán khoảng cách giữa bất kỳ hai tập đối tượng hoặc điểm nào, nhiều phương pháp tiền xử lý và tối ưu hóa có thể dùng. Có một phương pháp nhóm các điểm gần nhau thành micro-cụm. Điều này hoàn thành bằng cách trước tiên tam giác hóa vùng R thành tam giác, sau đó kết hợp các điểm gần nhau trong cùng tam giác thành micro-cụm, dùng phương pháp tương tự BIRCH hoặc DBSCAN.
Bằng cách xử lý micro-cụm thay vì điểm đơn lẻ, toàn bộ tính toán được giảm. Sau đó, tiền tính toán có thể thực hiện để xây dựng hai loại chỉ mục nối dựa trên tính toán đường đi ngắn nhất:
- Chỉ mục VV, cho mọi cặp đỉnh chướng ngại vật.
- Chỉ mục MV, cho mọi cặp micro-cụm và đỉnh chướng ngại vật. Chỉ mục này giúp tối ưu hóa hiệu suất tổng thể hơn.
Với tiền xử lý và tối ưu hóa như vậy, khoảng cách giữa bất kỳ hai điểm nào (ở mức độ chi tiết micro-cụm) có thể tính hiệu quả. Do đó, quy trình cụm hóa có thể thực hiện theo cách tương tự thuật toán k-medoids hiệu quả điển hình, bao gồm CLARANS, và đạt chất lượng cụm hóa tốt cho tập dữ liệu lớn.