Luận án thuật toán hình học tính toán theo phương pháp đường định hướng của Trịnh Minh Đức

Luận án nghiên cứu các thuật toán giải bài toán hình học tính toán dựa trên phương pháp đường định hướng, lưới Delaunay và tìm đường đi ngắn nhất.

• Tác giả: Trịnh Minh Đức
• Người hướng dẫn: TS. Đặng Thị Oanh
• Trường học: Đại học Thái Nguyên - Trường Đại học Công nghệ Thông tin và Truyền thông
• Chuyên ngành: Khoa học máy tính
• Đề tài: Một số thuật toán hữu hiệu giải bài toán trong hình học tính toán dựa trên phương pháp đường định hướng
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2025
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng quan thuật toán hình học tính toán theo đường định hướng

Hình học tính toán đóng vai trò cốt lõi trong xử lý đồ họa máy tính và mô hình hóa hình học hiện đại. Các công trình nghiên cứu tại Đại học Thái Nguyên đã mang đến những bước tiến đột phá cho lĩnh vực này. Nổi bật là đề tài nghiên cứu phương pháp đường định hướng của nhóm tác giả Trường Đại học Công nghệ Thông tin và Truyền thông. Công trình tập trung giải quyết các bài toán tối ưu hình học có dữ liệu rời rạc. Hướng tiếp cận này giúp khắc phục triệt để các hạn chế cố hữu của những thuật toán cổ điển. Các phương pháp truyền thống thường yêu cầu trải phẳng hoặc biến đổi tọa độ phức tạp. Việc này tiêu tốn nhiều tài nguyên tính toán và dễ gây sai số tích lũy trên bề mặt cong ba chiều. Ngược lại, phương pháp đường định hướng vận dụng trực tiếp các đặc trưng hình học nội tại của bề mặt. Thuật toán phân tích chuỗi tam giác liền kề để tìm đường trắc địa ngắn nhất một cách chính xác. Mô hình này mở ra giải pháp xử lý dữ liệu không gian lớn với độ phức tạp tính toán thấp. Các kết quả lý thuyết đã được chứng minh chặt chẽ về tính hội tụ cũng như tính tối ưu toàn cục.

1.1. Bối cảnh nghiên cứu tại Đại học Thái Nguyên

Luận án tiến sĩ của tác giả Trịnh Minh Đức được thực hiện tại Đại học Thái Nguyên dưới sự hướng dẫn của các chuyên gia đầu ngành. Nghiên cứu thuộc khuôn khổ đề tài quỹ Nafosted về tối ưu hóa hình học rời rạc. Đề tài giải quyết nhu cầu cấp thiết trong lĩnh vực khoa học máy tính ứng dụng. Các hệ thống mô phỏng 3D hiện đại đòi hỏi tốc độ xử lý dữ liệu thời gian thực rất cao. Những thuật toán cũ không còn đáp ứng tốt khi số lượng điểm dữ liệu tăng vọt. Việc xây dựng thuật toán tính toán hình học mới mang ý nghĩa khoa học và thực tiễn sâu sắc. Kết quả nghiên cứu khẳng định vị thế học thuật của Đại học Thái Nguyên trong lĩnh vực công nghệ cao.

1.2. Khái niệm cơ bản về đường định hướng

Đường định hướng là công cụ toán học quan trọng dùng để dẫn đường và định vị không gian trên các bề mặt đa diện. Khái niệm này xuất phát từ việc theo dõi hướng đi liên tục qua các mặt phẳng tam giác kề nhau. Thay vì biến đổi tọa độ phức tạp, đường định hướng duy trì mối liên hệ góc và phương vị trực tiếp trong không gian ba chiều. Khi kết hợp với các đường tròn định hướng ngoại tiếp, phương pháp cho phép xác định chính xác vị trí các đỉnh lân cận. Cơ chế định hướng giúp kiểm soát chặt chẽ quá trình mở rộng vùng tìm kiếm. Thuật toán luôn duy trì tính ổn định số học trong suốt quá trình xử lý. Đây là nền tảng lý thuyết cốt lõi để xây dựng các giải thuật tìm kiếm tối ưu.

II. Thách thức với thuật toán hình học tính toán theo đường định hướng

Xử lý hình học tính toán trên không gian ba chiều đối mặt với nhiều rào cản thuật toán phức tạp. Bài toán tìm đường đi ngắn nhất giữa hai điểm trên bề mặt đa diện là một ví dụ điển hình. Kỹ thuật truyền thống phổ biến nhất trước đây là phương pháp lật phẳng từng bước. Phương pháp này trải các tam giác liền kề lên một mặt phẳng 2D chung để quy đổi bài toán không gian về hình học phẳng. Tuy nhiên, kỹ thuật lật phẳng bộc lộ nhiều nhược điểm nghiêm trọng khi ứng dụng vào thực tế. Quá trình quay mặt phẳng liên tục làm phát sinh sai số làm tròn số học rất lớn. Khi xử lý mô hình chứa hàng triệu tam giác, hiện tượng chồng lấn hình học xảy ra thường xuyên. Việc quản lý các ma trận chuyển đổi tọa độ cũng đòi hỏi bộ nhớ khổng lồ. Hơn nữa, thao tác lật phẳng làm mất đi tính toàn vẹn cấu trúc toàn cục của vật thể 3D. Điều này gây khó khăn cho việc xử lý các bề mặt có độ cong biến thiên phức tạp hoặc bề mặt tự giao. Nghiên cứu tại Đại học Thái Nguyên đã phân tích rõ những điểm nghẽn này để tìm kiếm hướng đột phá mới.

2.1. Hạn chế của kỹ thuật lật phẳng truyền thống

Kỹ thuật lật phẳng từng bước đòi hỏi trải các tam giác không gian xuống mặt phẳng 2D. Quá trình này yêu cầu chuỗi phép quay và biến đổi ma trận liên tiếp. Khi số lượng tam giác tăng lên, sai số làm tròn số học tích lũy rất nhanh. Sai số này dẫn đến hiện tượng trượt điểm và xác định sai cạnh giao nhau. Thậm chí các tam giác có thể bị đảo ngược thứ tự đỉnh trong quá trình chiếu. Ngoài ra, thuật toán lật phẳng không thể xử lý tốt các trường hợp bề mặt gấp khúc đột ngột. Chi phí tính toán tăng theo cấp số nhân khiến hệ thống dễ bị quá tải bộ nhớ. Đây là nút thắt lớn cản trở việc xử lý dữ liệu 3D quy mô lớn.

2.2. Vấn đề duy trì cấu trúc lưới tam giác Delaunay

Lưới tam giác Delaunay là tiêu chuẩn vàng trong phân chia không gian rời rạc nhờ tính chất đường tròn rỗng. Mọi tam giác trong lưới đều không chứa bất kỳ điểm nào khác bên trong đường tròn ngoại tiếp của nó. Tuy nhiên việc tái lập lưới Delaunay khi cập nhật hoặc hợp nhất các tập điểm 3D rất phức tạp. Các phương pháp chia để trị truyền thống thường gặp khó khăn tại vùng biên ghép nối. Việc xác định các cạnh Delaunay hợp lệ đòi hỏi liên tục kiểm tra vị trí tương đối của hàng loạt điểm biên. Nếu không có tiêu chí định hướng rõ ràng, thuật toán dễ rơi vào vòng lặp kiểm tra vô tận. Thời gian xử lý khi đó tăng vọt và làm giảm độ tin cậy của mô hình hình học.

III. Phương pháp thuật toán hình học tính toán theo đường định hướng

Luận án tại Đại học Thái Nguyên đề xuất giải pháp đột phá bằng cách tiếp cận trực tiếp trong không gian ba chiều. Ý tưởng chủ đạo là sử dụng phương pháp đường định hướng để loại bỏ hoàn toàn thao tác lật phẳng. Thuật toán định vị đường đi ngắn nhất thông qua việc phân tích đặc trưng định hướng của các dải tam giác kề nhau. Khi hai tam giác chia sẻ một cạnh chung, một đường tròn định hướng được thiết lập đi qua cạnh này. Đường tròn hoạt động như một mốc kiểm tra hình học nghiêm ngặt. Thuật toán xác định chính xác các điểm lân cận thuộc tập hợp điểm mà không cần chiếu phẳng tọa độ. Các phép tính định hướng dựa trên việc kiểm tra dấu của diện tích định hướng tam giác và tiếp tuyến chung ngoài của các đường tròn. Nhờ vậy, giải thuật luôn đảm bảo tính chính xác tuyệt đối về mặt số học. Độ phức tạp tính toán giảm đáng kể so với các phương pháp cũ. Cấu trúc dữ liệu được tối ưu hóa giúp tiết kiệm dung lượng bộ nhớ vận hành. Thuật toán dễ dàng mở rộng để xử lý các mô hình lưới đa diện phức tạp trong thực tế.

3.1. Tìm đường đi ngắn nhất không cần lật phẳng

Thuật toán mới xác định đường trắc địa ngắn nhất trực tiếp trên các dải tam giác kề nhau trong không gian 3D. Thay vì mở phẳng các mặt tam giác, thuật toán theo dõi góc định hướng xuyên suốt qua từng cạnh giao. Nguyên lý hình học của đường định hướng đảm bảo đường đi tìm được luôn là ngắn nhất cục bộ và toàn cục. Giải thuật tiến hành duyệt qua các đỉnh biên dựa trên điều kiện tiếp xúc của đường tròn định hướng. Quá trình tính toán chỉ sử dụng các phép toán số học cơ bản trên tọa độ gốc. Nhờ đó, sai số làm tròn được triệt tiêu hoàn toàn. Tốc độ tìm kiếm đường đi nhanh gấp nhiều lần so với các kỹ thuật chiếu phẳng truyền thống.

3.2. Tối ưu hóa hợp nhất lưới Delaunay bằng đường tròn định hướng

Luận án phát triển kỹ thuật sử dụng đường tròn định hướng để tối ưu hóa việc hợp nhất hai lưới Delaunay. Khi ghép nối hai tập điểm, thuật toán kiểm tra sự tồn tại của đường tròn ngoại tiếp đi qua cạnh chung Delaunay. Các tiếp tuyến chung ngoài giữa hai đường tròn được tính toán chính xác để phân loại tập điểm lân cận. Những điểm nằm ngoài vùng giới hạn của tiếp tuyến sẽ bị loại bỏ ngay lập tức mà không cần kiểm tra chi tiết. Thuật toán nhanh chóng xác định tam giác Delaunay mới mà không gây xung đột hình học. Kỹ thuật chia để trị kết hợp đường tròn định hướng giúp giảm thời gian xử lý xuống mức tối ưu. Lưới tam giác sau khi hợp nhất luôn giữ vững tính chất rỗng toàn vẹn.

IV. Ứng dụng của thuật toán hình học tính toán theo đường định hướng

Nghiên cứu về phương pháp đường định hướng của Đại học Thái Nguyên mở ra tiềm năng ứng dụng to lớn trong công nghệ hiện đại. Trong ngành robot tự hành, thuật toán hỗ trợ lập lộ trình di chuyển tối ưu trên các địa hình gồ ghề ba chiều. Robot có thể tránh vật cản chính xác mà không tốn nhiều năng lượng xử lý tính toán. Trong lĩnh vực đồ họa máy tính và game 3D, thuật toán giúp tái tạo bề mặt vật thể nhanh chóng từ đám mây điểm lớn. Các mô hình phức tạp được hiển thị mượt mà với độ chi tiết cao mà không làm giảm tốc độ khung hình. Ngoài ra, giải pháp còn đóng vai trò then chốt trong hệ thống thông tin địa lý GIS để phân tích bề mặt địa hình tự nhiên. Ngành cơ khí chính xác và in 3D cũng hưởng lợi lớn từ việc tối ưu hóa đường chạy dao và đường quét vật liệu. Các kết quả của luận án là minh chứng cho giá trị thực tiễn của nghiên cứu toán tin ứng dụng tại Việt Nam. Đây là tiền đề quan trọng để phát triển các phần mềm kỹ thuật cao phục vụ công nghiệp 4.0.

4.1. Ứng dụng trong điều hướng robot tự hành và mô phỏng 3D

Trong lĩnh vực robot tự hành, thuật toán hỗ trợ việc định tuyến di chuyển tối ưu trên các bề mặt đa diện phức tạp. Nhờ khả năng tìm đường đi ngắn nhất không cần lật phẳng, robot phản ứng nhanh nhạy với các biến đổi địa hình. Bộ xử lý nhúng trên thiết bị không bị quá tải tính toán ma trận. Đối với công nghệ đồ họa máy tính, thuật toán hỗ trợ dựng hình thời gian thực cho các mô hình đa giác lớn. Lưới tam giác được tinh chỉnh liên tục giúp tạo chuyển động mượt mà cho nhân vật và cảnh quan ảo. Các nhà phát triển game và ứng dụng thực tế ảo có thể tối ưu hóa hiệu năng phần cứng đáng kể.

4.2. Tiềm năng trong hệ thống GIS và gia công cơ khí

Hệ thống thông tin địa lý GIS đòi hỏi năng lực phân tích dữ liệu bề mặt số học với độ chính xác cao. Kỹ thuật đường định hướng giúp xử lý hiệu quả mô hình số độ cao DEM và phân tích lưu vực dòng chảy. Quá trình tính toán đường thoát nước hoặc tuyến cáp ngầm trên địa hình thực tế diễn ra nhanh chóng. Trong ngành sản xuất chế tạo, thuật toán hỗ trợ tối ưu hóa đường đi của đầu dao gia công CNC và vòi phun in 3D. Việc loại bỏ các bước tính toán dư thừa giúp giảm thời gian gia công và kéo dài tuổi thọ thiết bị. Đóng góp nghiên cứu này thúc đẩy mạnh mẽ quá trình tự động hóa sản xuất thông minh.

Trích đoạn nội dung tài liệu

phần Mở đầu, lưới tam giác Delaunay đóng vai trò quan trọng trong nhiều lĩnh vực ứng dụng thực tiễn. Do đó, việc nghiên cứu và phát triển các thuật toán xây dựng lưới tam giác Delaunay với tốc độ nhanh và hiệu quả tính toán cao ngày càng trở nên cần thiết và có ý nghĩa thực tiễn sâu sắc. Có rất nhiều những thuật toán tuần tự đã được cài đặt để xây dựng lưới tam giác Delauany. Với các thuật toán tuần tự trên cơ bản đã xây dựng được lưới tam giác Delaunay từ tập các điểm đã cho, tuy nhiên các thuật toán tuần tự thường yêu cầu thời gian tính toán lớn.

Do vậy việc xây dựng các thuật toán song song nhằm mang lại hiệu quả cao hơn trở nên rất quan trong để làm giảm thời gian tính toán [59, 47, 68, 96, 17, 67, 36, 20, 101, 48, 87, 37, 60]. Nhìn chung, các thuật toán tuần tự cho việc xây dựng lưới tam giác Delaunay chia thành năm hướng tiếp cận chính: thuật toán chia để trị (divide and conquer) [27, 39], thuật toán sử dụng đường quét (sweepline) [34], thuật toán tăng dần (incremental) [19, 38, 39, 40, 69], sử dụng các thuật toán bao gói [28, 62] và hướng tiếp cận dựa trên mối quan hệ giữa lưới tam giác Delaunay và bao lồi trong một chiều cao hơn [10]. Phần lớn các thuật toán hiệu quả hiện nay nhằm xây dựng lưới tam giác Delaunay, bao gồm các thuật toán tuần tự và song song, đều được phát triển dựa trên chiến lược chia để trị [27, 39, 56, 84, 102]. Những thuật toán này được đặc trưng bởi chi phí tính toán của các giai đoạn phân chia và ghép nối.

Thuật toán của Lee va Schachter [56] là một thuật toán tuần tự hiệu quả dùng để xây dựng lưới tam giác Delaunay, với độ phức tạp thời gian tối wu IA O(nlogn)).1: Lưới tam giác Delaunay. Guibas và Stolfi [39] đã đề xuất một thuật toán hiệu quả để xây dựng lưới tam giác Delaunay với độ phức tạp thời gian OÓ(» logø). Thuật toán này tuân theo chiến lược chia để trị cổ điển, trong đó bài toán lớn được chia đệ quy thành các bài toán con nhỏ hơn, và kết quả của các bài toán con được kết hợp lại để thu được nghiệm của bài toán ban đầu. Một điểm đặc trưng nổi bật của thuật toán là việc áp dụng cấu trúc dữ liệu guad-edge, cho phép thao tác linh hoạt và hiệu quả trong bước hợp nhất hai lưới tam giác Delaunay được tạo từ các tập điểm con liền kề.

Các bước chính của thuật toán bao gồm: ¡. Sắp xếp tập hợp các điểm V theo thứ tự từ điển tăng dần dựa trên hoành độ. Loại bỏ bất kỳ điểm trùng lặp nào. Tạp điểm W được chia thành các tập con phai va trai Vp va Vz, sao cho mỗi tập chứa số lượng điểm xấp xỉ bằng nhau.

Đệ quy xây dựng hai lưới tam giác Delaunay: DT(Wr) và DT(Vn). Ghép nối DT(W¿) và DT(Vạ) để tạo thành DT(V¿,U W?). Trong số các bước trên, bước ghép nối là bước quan trọng và phức tạp nhất của thuật toán. Như được minh họa trong Hình 1.2, các cạnh Delaunay mới được thêm 10 vào có thể tạo thành một dãy liên tiếp theo phương thẳng đứng, do đó quá trình ghép nối được tiến hành tuần tự từ dưới lên.

Để tiến hành ghép nối DT(W¡,) và DT(W), thuật toán sử dụng bao lồi CH(V„UVWR), có thể được xác định trong thời gian O(n) tiv hop hai bao 1éi CH(V¿) và CH(W?). Hợp của hai bao lồi này tạo ra hai tiếp tuyến chung: tiếp tuyến trên và tiếp tuyến dưới, đóng vai trò là céc canh Delaunay trong DT(Vz U Vr). Quá trình ghép nối bắt đầu từ tiếp tuyến chung dưới của hai bao lồi, còn được gọi là đường cơ sở. Từ đường cơ sở này, thuật toán tiến hành lựa chọn một điểm thứ ba liền kề với hai điểm đầu mút nhằm tạo thành một tam giác Delaunay dựa trên tiêu chí “đường tròn ngoại tiếp rỗng”.

Cụ thể, thuật toán có thể: e Kết nối điểm đầu mút bên trái (thuộc W„) với một điểm liền kề bên phải (thuộc Vn), hoặc e Kết nối điểm đầu mút bên phải với một điểm liền kề bên trái, để tạo thành một cạnh Delaunay méi trong DT(Vz U Vr). Canh Delaunay mdi nay sé thay thé đường cơ sở hiện tại để trở thành đường cơ sở tiếp theo. Quá trình được lặp lại cho đến khi đường cơ sở đi đến tiếp tuyến chung trên, khi đó việc ghép nối hoàn tất.2: Minh hoa quá trình ghép nối hai lưới tam giác Delaunay liền kề. Một ví dụ minh họa cụ thể cho quá trình ghép nối được trình bày trong Hình 1.

11 Xét tam giác Alzr¡ với đường tròn ngoại tiếp Ơn, trong đó Ơg không chứa điểm nào của W„ẹ bên trong. Tương tự, tam giác Arll có đường tròn ngoại tiếp Cr, không chứa điểm nào của W,. Trong trường hợp này, có hai khả năng kết nối: nối /¡ với r, hoặc nối rị với !. Tuy nhiên, nếu như Œp chứa điểm iị bên trong, thì kết nối hợp lệ là cạnh [r,i], và cạnh này sẽ được thêm vào như một cạnh Delaunay mới trong DT(W,, U Vr).3: Minh hoa cu thé qua trinh ghép néi DT(V;) va DT(Vg) dé tao thanh DT(Vz UV).

Bên cạnh d6, Dwyer [27] da đề xuất một cải tiến trong cách cài đặt thuật toán chia để trị nhằm xây dựng lưới tam giác Delaunay cho tập ø > 3 điểm trong mặt phẳng. Sự điều chỉnh này giúp giảm độ phức tạp xuống còn O(nloglogn). Tuy nhiên, phương pháp này chỉ thực sự hiệu quả trong các trường hợp mà ø < 21%, 12 1. Tổng quan về bài toán tính chính xác các đường đi ngắn nhất trên bề mặt đa diện Bài toán tính chính xác các đường đi ngắn nhất từ một điểm nguồn cố định đến tất cả các đỉnh trên một bề mặt đa diện là một bài toán được nghiên cứu rộng rãi trong hình học tính toán.

Để tính chính xác đường đi ngắn nhất, Sharir và Schorr [92] lần đầu tiên trình bày một thuật toán O(n? logn) chay trén mot mặt đa diện lồi, trong đó ø là số đỉnh của đa diện. Thuật toán này sau đó đã được cải tiến bởi Mount [66] thành O(n? logn). Thuat todn cha Mount dua trén 3 quan sat rat quan trong sau: i. Gia stt ring đường đi ngắn nhất từ điểm s đến điểm ¿ trên bề mặt khối đa diện lồi đi qua phần trong của các cạnh eq,ea,.

Khi đó đường đi ngắn nhất trên thực tế có thể được xác định bằng phép lật dãy các mặt kề. Khi đó, đường đi ngắn nhất tìm được nối hai điểm s và ¿ trên dãy mặt đã được trải phẳng có dạng một đoạn thẳng. Hai đường đi ngắn nhất, xuất phát từ cùng một đỉnh đến hai điểm khác nhau không cắt nhau. Một đường đi ngắn nhất bất kỳ không thể đi qua đỉnh của khối đa diện lồi.

Đối với một bề mặt đa diện tùy ý, Mitchell, Mount va Papadimitriou [64] da đưa ra một thuật toán có độ phức tạp Ó(x2logn) kế thừa mô hình của thuật toán Dijkstra [26]. Việc triển khai thuật toán tìm đường đi ngắn nhất chính xác này đã được thực hiện bởi Surazhsky et al. [97] với một số cải tiến và mở rộng vào năm 2005. Năm 1996, Chen và Han [18] đã đưa ra một thuật toán với độ phức tạp về thời gian là O(n”), dua trén mot quan sAt quan trong "one angle one split" dé xc định đường đi ngắn nhất toàn cục từ một điểm nguồn đã cho đến bất kỳ điểm nào trên bề mặt khối đa diện.

Thuật toán này đã được Kaneva và O'Rourke [49] triển khai vào năm 2000. Xin và Wang [103] đã trình bày một thuật toán dựa trên khả năng hiển thị, với tốc độ hội tụ nhanh, để xác định chính xác đường đi ngắn nhất cục bộ từ một điểm nguồn đến một điểm đích trên bề mặt đa diện (đã được tam giác phân hóa). Mặc dù Xin và Wang [104] đã tăng tốc thuật toán của Chen và Han, việc tìm kiếm các lời giải chính xác vẫn đòi hỏi thời gian cao đối với các mô hình lớn. Sau đó, Xin và Wang [105] đã áp dụng các cải tiến của họ cho thuật toán 13 của Chen và Han tới các phiên bản khác nhau của bài toán đường đi ngắn nhất.

Ho đã chứng minh rằng thuật toán cải tiến này có thể được mở rộng tự nhiên sang phiên bản "multiple sources, any destination". Để giải bài toán tìm đường đi ngắn nhất khi miền là các bề mặt đa diện, một số tác giả đã xem xét bài toán tìm đường đi ngắn nhất giữa hai điểm bên trong một dãy các tam giác liền kề (được xây dựng từ bề mặt đa diện), ví dụ như trong [76], [103]. Kỹ thuật lật phẳng dãy mặt tam giác liền kề, với tính chất bảo toàn góc và khoảng cách, thường được sử dụng để giải quyết bài toán này. Cụ thể, Pham-Trong và cộng sự trong [76] đã đưa ra một thuật toán để tính toán đường đi ngắn nhất giữa hai điểm bên trong một dãy các tam giác.

Đầu tiên, họ chọn một dãy mặt tam giác liền kề bất kỳ nối hai điểm mà họ cần xác định đường đi ngắn nhất, sau đó họ sử dụng kỹ thuật lật phẳng để đưa dãy mặt tam giác liền kề trong không gian ba chiều (3D) về một dãy mặt tam giác liền kề trong không gian hai chiều (2D). Sau khi lật phẳng, họ xem xét dãy mặt phẳng và sử dụng kỹ thuật "beam propagation" để tìm đường đi ngắn nhất. Tuy nhiên, họ không đưa ra chi tiết thuật toán cũng như độ phức tạp của thuật toán này. Năm 2007, Xin và Wang [103] đã giới thiệu một quá trình lật phẳng dãy các tam giác và một thuật toán để tính toán đường đi ngắn nhất giữa hai điểm bên trong dãy các tam giác.

Độ phức tạp tính toán của thuật toán này là O(n?), trong đó ø là số cạnh kề của dãy mặt tam giác liền kề. Tóm lại, hầu hết các kết quả nghiên cứu trên đều có một điểm chung đó là sử dụng kỹ thuật lật phẳng để đưa bài toán tìm đường đi ngắn nhất giữa hai điểm trên dãy mặt tam giác liền kề trong 3D về bài toán tìm đường đi ngắn nhất giữa hai điểm trên dãy tam giác liền kề trong 2D. Tuy nhiên trong thực tế, ảnh của dãy mặt tam giác liền kề sau khi thực hiện kỹ thuật lật phẳng có thể xảy ra trường hợp các mặt tam giác đè lên nhau. Cả Pham- Trong và cộng sự cũng như Xin và Wang đều không đề cập tới và không chứng minh về tính đúng đắn của thuật toán của họ trong trường hợp như vậy.