Luận án tiến sĩ: Bài toán tìm bao lồi cho tập hữu hạn các điểm và hình tròn

Luận án tiến sĩ toán học phân tích hus bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn, xây dựng cơ sở lý luận, kiểm chứng thực nghiệm, đóng góp tri thức mới cho

• Tác giả: Nguyễn Kiều Linh
• Người hướng dẫn: TS. Hoàng Nam Dũng
• Trường học: Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
• Chuyên ngành: Toán ứng dụng
• Đề tài: Bài Toán Tìm Bao Lồi Của Tập Hữu Hạn Các Điểm Hoặc Các Hình Tròn
• Loại tài liệu: Luận án tiến sĩ
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• 1. CHƯƠNG 1: KIẾN THỨC CHUẨN BỊ
• 2. CHƯƠNG 2
• 3. CHƯƠNG 3
• 4. CHƯƠNG 4
• DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH VẼ
• DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về bài toán bao lồi cho tập điểm và hình tròn

Bài toán tìm bao lồi cho tập hữu hạn điểm và hình tròn là một trong những vấn đề quan trọng trong hình học tính toán. Bài toán này không chỉ có ứng dụng trong đồ họa máy tính mà còn trong nhiều lĩnh vực khác như nhận dạng mẫu, xử lý hình ảnh và tìm đường đi ngắn nhất cho robot. Việc hiểu rõ về bài toán này sẽ giúp các nhà nghiên cứu và kỹ sư phát triển các thuật toán hiệu quả hơn.

1.1. Khái niệm cơ bản về bao lồi và tập điểm

Bao lồi của một tập điểm là hình đa diện nhỏ nhất chứa tất cả các điểm trong tập đó. Để tính toán bao lồi, cần hiểu rõ các khái niệm như điểm cực biên và biên của bao lồi.

1.2. Ứng dụng của bài toán bao lồi trong thực tiễn

Bài toán bao lồi có nhiều ứng dụng thực tiễn, từ việc xác định vị trí tối ưu trong không gian đến việc xây dựng các mô hình hình học phức tạp trong đồ họa máy tính.

II. Thách thức trong việc giải bài toán bao lồi cho tập điểm

Mặc dù bài toán bao lồi đã được nghiên cứu nhiều, nhưng vẫn còn nhiều thách thức trong việc tối ưu hóa thuật toán. Các vấn đề như độ phức tạp tính toán và khả năng mở rộng của thuật toán là những yếu tố cần được xem xét.

2.1. Độ phức tạp tính toán của các thuật toán hiện tại

Nhiều thuật toán hiện tại như Quickhull và Divide-and-Conquer có độ phức tạp tính toán khác nhau. Việc hiểu rõ độ phức tạp này giúp cải thiện hiệu suất của thuật toán.

2.2. Khó khăn trong việc xử lý dữ liệu lớn

Khi làm việc với dữ liệu lớn, các thuật toán hiện tại thường gặp khó khăn trong việc duy trì hiệu suất. Cần có các phương pháp mới để tối ưu hóa quá trình tính toán.

III. Phương pháp cải tiến thuật toán bao lồi cho tập điểm

Để giải quyết các thách thức trong bài toán bao lồi, nhiều phương pháp cải tiến đã được đề xuất. Những cải tiến này không chỉ giúp tăng tốc độ tính toán mà còn nâng cao độ chính xác của kết quả.

3.1. Cải tiến thuật toán Quickhull

Thuật toán Quickhull đã được cải tiến để giảm số lượng phép toán xác định sự định hướng, từ đó tăng tốc độ tính toán lên gấp 3 lần so với phiên bản ban đầu.

3.2. Kỹ thuật hạn chế trong tính toán bao lồi

Sử dụng kỹ thuật hạn chế giúp giảm số chiều của tập điểm, từ đó làm cho các tính toán trở nên dễ dàng và nhanh chóng hơn.

IV. Giới thiệu thuật toán QuickhullDisk cho tập hình tròn

Thuật toán QuickhullDisk được giới thiệu như một phương pháp mới để tìm bao lồi cho tập hình tròn. Thuật toán này không chỉ hiệu quả mà còn dễ dàng áp dụng trong nhiều tình huống thực tế.

4.1. Độ phức tạp và tính đúng đắn của thuật toán

Thuật toán QuickhullDisk đã được chứng minh về độ phức tạp tính toán trong trường hợp xấu nhất và trung bình, đảm bảo tính đúng đắn của kết quả.

4.2. Kết quả thực nghiệm với thuật toán QuickhullDisk

Các thử nghiệm cho thấy thuật toán QuickhullDisk có thể tăng tốc độ tính toán lên khoảng 3,5 lần so với các thuật toán hiệu quả khác.

V. Ứng dụng của bài toán bao lồi trong xác định vị trí tối ưu

Bài toán bao lồi không chỉ dừng lại ở việc tính toán hình học mà còn có thể được áp dụng trong việc xác định vị trí tối ưu cho các bài toán thực tiễn. Việc sử dụng bao lồi như một bước tiền xử lý có thể giúp cải thiện đáng kể hiệu suất của các thuật toán tối ưu.

5.1. Tính toán bao lồi như bước tiền xử lý

Việc tính toán bao lồi trước khi thực hiện bài toán tối ưu không trơn giúp tăng tốc đáng kể so với việc không sử dụng kỹ thuật này.

5.2. Kỹ thuật hạn chế cho bài toán xác định tam giác phân Delaunay

Kỹ thuật hạn chế tính bao lồi dưới hiệu quả cho lớp bài toán xác định tam giác phân Delaunay và biểu đồ Voronoi đã được trình bày, cho thấy sự cải thiện về tốc độ tính toán.

VI. Kết luận và triển vọng tương lai của bài toán bao lồi

Bài toán bao lồi cho tập điểm và hình tròn vẫn là một lĩnh vực nghiên cứu sôi động với nhiều thách thức và cơ hội. Các nghiên cứu trong tương lai có thể tập trung vào việc phát triển các thuật toán mới và cải tiến các phương pháp hiện tại để đáp ứng nhu cầu ngày càng cao trong thực tiễn.

6.1. Hướng nghiên cứu tiếp theo trong bài toán bao lồi

Nghiên cứu có thể tập trung vào việc phát triển các thuật toán song song và phân tán để xử lý dữ liệu lớn trong thời gian thực.

6.2. Tầm quan trọng của bài toán bao lồi trong các lĩnh vực khác

Bài toán bao lồi có thể được áp dụng trong nhiều lĩnh vực khác nhau, từ khoa học máy tính đến kỹ thuật, mở ra nhiều cơ hội nghiên cứu mới.

Nội dung chính

Tổng quan về luận án

Trong kỷ nguyên số hóa và bùng nổ dữ liệu không gian, bài toán xác định bao lồi (Convex Hull) giữ vị trí nền tảng trong hình học tính toán (Computational Geometry), đóng vai trò then chốt trong xử lý ảnh, thị giác máy tính, nhận dạng mẫu, hệ thống thông tin địa lý (GIS), điều khiển robot tự hành và tối ưu hóa không trơn. Luận án tiến sĩ toán học "Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn" của nghiên cứu sinh Nguyễn Kiều Linh (chuyên ngành Toán ứng dụng, mã số 9460112.01, Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội, 2019; người hướng dẫn: TS. Hoàng Nam Dũng và PGS. Phan Thành An) đã giải quyết triệt để các nút thắt tính toán cốt lõi trong các thuật toán bao lồi kinh điển.

Nghiên cứu tập trung vào hai khoảng trống tri thức (research gaps) mang tính sống còn:

1. Sự dư thừa chi phí tính toán của các phép thử định hướng hình học (orient predicate) trong các biến thể Quickhull và thuật toán gói quà (Gift Wrapping) trên không gian đa chiều $\mathbb{R}^d$.
2. Sự thiếu hụt một thuật toán kiểu chia để trị kết hợp Quickhull hiệu quả, có chứng minh toán học hoàn chỉnh về độ phức tạp trung bình và phân tích độ mượt (smoothed analysis) cho tập các đối tượng phi điểm — cụ thể là tập hữu hạn các hình tròn đóng trong $\mathbb{R}^2$.

Luận án thiết lập và kiểm định 4 câu hỏi nghiên cứu ($Q_1 - Q_4$) và 4 giả thuyết khoa học tương ứng ($H_1 - H_4$):

• $Q_1$: Liệu có thể giảm thiểu số lượng phép toán định hướng bậc cao trong phân chia không gian của thuật toán Quickhull 2D mà không làm mất tính toàn vẹn hình học? $\to H_1$: Tích hợp biến lưu vết cực đại/cực tiểu và vector định hướng sẽ giảm ít nhất 50% số phép tính định thức orient.
• $Q_2$: Cơ chế chiếu giảm chiều không gian nào tối ưu hóa được vùng tìm kiếm của thuật toán gói quà trong $\mathbb{R}^d$? $\to H_2$: Kỹ thuật miền hạn chế tốt nhất (Best Restricted Region) cho phép cắt giảm tối thiểu 35-40% thời gian quét diện đa diện.
• $Q_3$: Thuật toán Quickhull có thể mở rộng trực tiếp cho tập đối tượng hình tròn $D = {d_1, d_2, \dots, d_n}$ với độ phức tạp trung bình tối ưu hay không? $\to H_3$: Thuật toán mới QuickhullDisk đạt độ phức tạp trung bình $O(n \log n)$ và cận trơn $O(n \log^2 n)$ dưới nhiễu Gaussian.
• $Q_4$: Việc xác định bao lồi dưới ($\operatorname{conv}_L(P)$) qua phép nâng paraboloid có tăng tốc giải thuật dưới vi phân trong bài toán vị trí tối ưu (Facility Location) hay không? $\to H_4$: Bước tiền xử lý bao lồi dưới giúp loại bỏ hơn 80% điểm không cực biên, tăng tốc độ hội tụ giải thuật tối ưu ít nhất 1.5 lần.

Khung lý thuyết của luận án xây dựng trên nền tảng Giải tích lồi (Rockafellar), Hình học tính toán tổ hợp (Preparata & Shamos, 1985), Phương pháp đường định hướng của Hoàng Xuân Phú (1987–1991) và Lý thuyết phân tích độ mượt (Smoothed Analysis của Spielman & Teng, 2004). Tác động đột phá được lượng hóa rõ nét: thuật toán Quickhull cải tiến tăng tốc gấp 3 lần so với phiên bản gốc; kỹ thuật miền hạn chế cho Gift Wrapping trong $\mathbb{R}^d$ giảm 40% thời gian xử lý; thuật toán QuickhullDisk vượt trội 3.5 lần so với thuật toán tăng dần của Olivier Devillers (1994); và kỹ thuật hạn chế bao lồi dưới tăng tốc 1.8 lần so với thuật toán của Phan Thành An và Trang (2015). Quy mô dữ liệu thử nghiệm đạt từ $10.000$ đến $2.000.000$ phần tử trên nhiều cấu hình hình học phức tạp.

Literature Review và Positioning

Lịch sử nghiên cứu bao lồi điểm khởi đầu từ thuật toán gói quà của Chand & Kapur (1970) và Jarvis (1973) với độ phức tạp $O(nh)$ (với $h$ là số đỉnh bao lồi), quét Graham (Graham, 1972) đạt $O(n \log n)$, chia để trị của Preparata & Hong (1977), thuật toán tăng dần của Kallay (1984), Quickhull của Bykat (1978) và Eddy (1977), cho đến thuật toán tối ưu đầu ra $O(n \log h)$ của Timothy Chan (1996). Trong không gian $\mathbb{R}^d$, Barber, Dobkin và Huhdanpaa (1996) chuẩn hóa thư viện Qhull dựa trên thuật toán Beneath-Beyond kết hợp Quickhull đa chiều với thời gian xấu nhất $O(n^{\lfloor d/2 \rfloor} / \lfloor d/2 \rfloor!)$.

Đối với tập đối tượng mở rộng là các hình tròn đóng trong $\mathbb{R}^2$, bài toán bắt đầu được chú ý từ thập niên 1990. David Rappaport (1992) đề xuất thuật toán chia để trị đạt $O(n \log n)$ thông qua thuật toán Hợp nhất (Merge algorithm) xoay các đường thẳng tựa song song. Năm 1994, Olivier Devillers cùng Mordecai Golin (1998) công bố thuật toán tăng dần (Incremental Algorithm) $O(n \log n)$ dựa trên phát hiện cấu trúc then chốt: một hình tròn có bán kính không vượt quá các hình tròn đã xét chỉ đóng góp tối đa một cung tròn vào biên bao lồi. Chen và cộng sự (1998) mở rộng phương pháp chia để trị song song đạt thời gian $O(\log^{1+\epsilon} n)$, trong khi Kim và cộng sự (2001) ứng dụng bao lồi đĩa tròn để tối ưu hóa quỹ đạo tránh vật cản cho robot.

Tuy nhiên, văn liệu tồn tại hai tranh luận lý thuyết và thực nghiệm sâu sắc:

1. Độ phức tạp trường hợp xấu nhất ($O(n^2)$) đối lập với hiệu năng thực tế ($O(n \log n)$): Các thuật toán như Quickhull thường bị đánh giá thấp trong các phân tích giải thuật kinh điển vì cận trên lý thuyết kém thuận lợi, nhưng trong thực tế lại vượt trội so với các thuật toán $O(n \log n)$ thuần túy do hệ số hằng số nhỏ và khả năng loại bỏ sớm dữ liệu nội tại. Spielman & Teng (2004) cùng Bläser & Sohler (2009) đã giải quyết mâu thuẫn này bằng công cụ smoothed analysis, nhưng chưa từng được áp dụng cho bài toán bao lồi hình tròn.
2. Chi phí đại số của phép định hướng ma trận định thức: Các cải tiến trước đây chủ yếu tập trung vào cấu trúc dữ liệu đồ thị hoặc phân chia không gian nhị phân (k-d tree), bỏ qua việc tối ưu hóa nội tại của từng phép thử định vị điểm (orientation test).

Luận án định vị chính xác vào giao điểm của việc tinh giản số lượng phép thử đại số và tái cấu trúc thuật toán chia nhánh. So với nghiên cứu của Barber et al. (1996), luận án không cần xây dựng toàn bộ cấu trúc diện đa diện phức tạp trong $\mathbb{R}^2$ mà triệt tiêu phép tính định thức qua việc lồng ghép điều kiện cực trị. So với thuật toán tăng dần của Devillers (1994), QuickhullDisk của luận án loại bỏ hoàn toàn yêu cầu tiền sắp xếp toàn bộ $n$ hình tròn theo thứ tự bán kính giảm dần ($O(n \log n)$ bắt buộc), từ đó đạt tốc độ vượt trội trên các tập dữ liệu có độ sâu lồi lớn.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mở rộng phương pháp đường định hướng của Hoàng Xuân Phú (1987, 1989, 1991) — vốn khởi nguồn từ lý thuyết điều khiển tối ưu có ràng buộc trạng thái — sang lĩnh vực tính toán rời rạc và hình học thuật toán. Bằng việc lượng hóa không gian nghiệm thông qua các vector định hướng, nghiên cứu thiết lập các mệnh đề toán học nền tảng:

"Một siêu phẳng có hướng $(x^1 x^2 \dots x^d)$ là một siêu phẳng chứa $d$ điểm độc lập affin $x^1, x^2, \dots, x^d$ trong không gian $\mathbb{R}^d$... Biểu thức orient có dạng một phương trình siêu phẳng qua $d$ điểm với vector pháp tuyến $\vec{\nu} = (\nu_1, \nu_2, \dots, \nu_d)$ và hệ số tự do $\nu_{d+1} = -\sum_{i=1}^d \nu_i z_i$."

Mệnh đề 2.2 trong luận án chứng minh rằng với bộ ba điểm $(p, q, r)$ và vector định hướng $\vec{t}_r$, mọi điểm $s \in S$ nằm ở phía dương của đoạn $pr$ bắt buộc phải thỏa mãn $\operatorname{orient}(t, r, s) > 0$. Điều này cho phép chuyển đổi phép tính định thức bậc cao thành một phép so sánh tọa độ vô hướng đơn giản: $s_x < r_x$ (khi $\vec{t}_r \parallel Oy$), giúp phân lập không gian mà không gây tổn thất thông tin hình học.

Đồng thời, luận án phát triển mô hình lý thuyết cho phép định hướng giữa đường tròn và đường thẳng có hướng: xác định vị trí tương đối thông qua khoảng cách đại số từ tâm hình tròn đến đường thẳng so với bán kính của nó, và hình thức hóa khái niệm tiếp tuyến phải $l(d, d')$ làm cầu nối giữa các đĩa cực biên.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp ba trụ cột lý thuyết:

1. Lý thuyết tập lồi và đa diện: Xây dựng nửa không gian tựa đóng $H^+$ và $H^-$ thông qua phương trình siêu phẳng tổng quát $\sum_{i=1}^d \nu_i x_i + \nu_{d+1} = 0$.
2. Kỹ thuật miền hạn chế chiếu tọa độ: Giảm số chiều không gian $\mathbb{R}^d \to \mathbb{R}^{d-1} \to \dots \to \mathbb{R}^2$, xác định tỷ số diện tích bao phủ cực tiểu để loại bỏ các điểm không thể thuộc bao lồi.
3. Khung phân tích độ phức tạp trơn (Smoothed Analysis Framework): Đánh giá thuật toán dưới mô hình nhiễu loạn ngẫu nhiên $\delta$, chứng minh cận kỳ vọng khi các điểm bị nhiễu bởi phân phối chuẩn $\mathcal{N}(0, \sigma^2)$ hoặc phân phối đều trong lân cận $\epsilon$.

Điều kiện biên (Boundary Conditions) được xử lý triệt để: trường hợp suy biến khi 3 điểm thẳng hàng ($\operatorname{orient}(p_i, p_{i+1}, p_{i+2}) = 0$) hoặc các đường tròn tiếp xúc, lồng nhau ($d_i \subseteq \operatorname{conv}(D)$) đều được giải quyết tự động bằng thuật toán lọc suy biến tuyến tính mà không làm tăng độ phức tạp tiệm cận.

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Nghiên cứu tuân thủ thế giới quan thực chứng (Positivism) và chủ nghĩa kiến tạo thuật toán (Algorithmic Constructivism). Thiết kế nghiên cứu đa tầng kết hợp giữa chứng minh toán học thuần túy (tính đúng đắn, sự hội tụ, độ phức tạp tiệm cận) và kiểm thử thực nghiệm quy mô lớn.

Mô hình thực nghiệm được phân cấp rõ ràng:

• Cấp độ 1: Tối ưu hóa vi mô mức lệnh đại số (giảm số lần gọi hàm orient).
• Cấp độ 2: Tối ưu hóa cấu trúc dữ liệu không gian 2D (tiền xử lý 8 điểm cực trị $q_1 \dots q_8$ phân tách 4 góc $Q_1, Q_2, Q_3, Q_4$).
• Cấp độ 3: Mở rộng không gian đối tượng hình học phức hợp (hình tròn đóng $D_i$ trong $\mathbb{R}^2$ và nâng chiều Paraboloid $z = (x-a)^2 + (y-b)^2$ trong $\mathbb{R}^3$).

Quy trình nghiên cứu rigorous

Quy trình nghiên cứu bao gồm thiết lập thuật toán, giải tích toán học và thẩm định thực nghiệm:

• Xây dựng quy tắc lọc: Xác định 8 điểm cực đặc biệt gồm tận cùng trái-trên ($q_1$), trên-trái ($q_2$), trên-phải ($q_3$), phải-trên ($q_4$), phải-dưới ($q_5$), dưới-phải ($q_6$), dưới-trái ($q_7$) và trái-dưới ($q_8$). Loại bỏ toàn bộ tập điểm nằm trong bát giác tạo bởi 8 điểm này.
• Kiểm thử độ tin cậy và tính hợp lệ: Đảm bảo tính hợp lệ cấu trúc (Construct Validity) qua việc chứng minh toán học mọi điểm cực biên thực sự của tập gốc $P$ đều thuộc tập biên của các phân vùng $S_1, S_2, S_3, S_4$.
• Môi trường thực thi: Toàn bộ thuật toán được lập trình bằng ngôn ngữ C thuần túy (không sử dụng thư viện bao lồi bên thứ ba để đảm bảo tính khách quan), biên dịch với tối ưu hóa cao, thực thi trên hệ thống phần cứng tiêu chuẩn: CPU Intel Core 2 Duo 2.0 GHz, 2GB RAM, hệ điều hành Linux.

Data và phân tích

Dữ liệu thực nghiệm được tổng hợp từ 5 mô hình phân phối không gian đại diện cho các trường hợp thử thách nhất trong hình học tính toán:

1. Dữ liệu hai đường tròn tách biệt: Tập điểm tạo ngẫu nhiên trong hai hình tròn bán kính $R = 4.500$, tâm tại $(4.500, 4.500)$ và $(8.500, 8.500)$.
2. Dữ liệu hình tròn rỗng (Annular Discs): Các điểm nguyên phân bố giữa hai đường tròn/ellipse đồng tâm với các tỷ số bán kính khác biệt.
3. Dữ liệu hai đường tròn đồng tâm hỗn hợp: 60% điểm nằm ở vành khăn ngoài, 40% điểm phân bố ngẫu nhiên bên trong lõi.
4. Dữ liệu hình vuông đặc: Phân phối đều bên trong hình vuông kích thước chuẩn.
5. Dữ liệu hình vuông rỗng: Phân phối giữa biên hình vuông ngoài $A$ và hình vuông trong $B$.

Mỗi kiểu dữ liệu được khảo sát qua 27 kịch bản độc lập với kích thước mẫu $n$ tăng dần từ $10.000$ đến $2.000.000$ điểm. Thời gian chạy (tính bằng giây) được đo lường chính xác và tính toán hệ số tăng tốc trung bình nhân (Geometric Mean Speedup Ratio).

Phát hiện đột phá và implications

Những phát hiện then chốt

1. Loại bỏ triệt để phép tính định hướng thừa: Thuật toán Quickhull cải tiến (Thuật toán 2.2) tận dụng kết quả tính $M = \operatorname{orient}(p, q, p_i)$ để cập nhật ngay lập tức các điểm xa nhất $r_1, r_2$ thông qua việc so sánh giá trị vô hướng với biến max/min. Số lần tính toán orient trong pha phân hoạch giảm từ $2n - 4$ xuống chính xác $n - 2$. Trong pha đệ quy Findhull, số phép tính giảm từ $2|P_k| + |S_2|$ xuống chỉ còn $|P_k|$, mang lại mức tiết kiệm 30% thời gian thực thi.

2. Đột phá từ Vector định hướng: Ứng dụng vector $\vec{t}_r \parallel Oy$ (Thuật toán 2.3) tạo ra cơ chế rây lọc sơ cấp: chỉ những điểm thỏa mãn $u_x < r_x$ mới cần gọi hàm orient để kiểm tra thuộc tính thuộc $S_1$, trong khi các điểm $u_x \ge r_x$ được chuyển tiếp trực tiếp sang kiểm tra $S_2$. Cơ chế này giảm thời gian chạy 23% độc lập.

3. Hiệu năng tối thượng của bước tiền xử lý 8 điểm cực: Bằng cách cô lập 4 vùng góc $Q_1, Q_2, Q_3, Q_4$ (Thuật toán 2.4), hơn 90% các điểm nằm sâu bên trong lõi đa giác bị loại bỏ ngay từ bước duyệt $O(n)$ đầu tiên. Khi tích hợp toàn diện cả ba kỹ thuật vào Thuật toán Quickhull mới (Thuật toán 2.5), hệ số tăng tốc đạt mức kỷ lục: gấp 3.0 lần (tăng 200% hiệu suất) so với Quickhull nguyên bản trên toàn bộ 5 tập dữ liệu mẫu.

4. Xác lập chuẩn mực mới cho bao lồi hình tròn với QuickhullDisk: Luận án chứng minh định lý toán học khẳng định QuickhullDisk tìm chính xác tập các đĩa cực biên $\operatorname{CH}(D)$. Độ phức tạp tính toán được chứng minh chặt chẽ:

• Trường hợp xấu nhất: $O(n^2)$.
• Trường hợp trung bình: $O(n \log n)$.
• Theo nghĩa Smoothed Analysis: Cận trên đạt mức $O(n \log^2 n)$ dưới nhiễu Gaussian và $O(n \cdot n^{2/3} \log n)$ dưới nhiễu đều. Thực nghiệm số trên tập dữ liệu hình tròn rỗng và hình vuông rỗng chứng minh QuickhullDisk chạy nhanh hơn thuật toán tăng dần của Olivier Devillers trung bình 3.5 lần.

5. Tăng tốc vượt bậc trong bài toán tối ưu không trơn và tam giác phân Delaunay:

"Tính bao lồi dưới $\operatorname{conv}_L(P)$ của tập hợp $P$ qua phép nâng $z_i = (x_i - q_x)^2 + (y_i - q_y)^2$... Chiếu tất cả các mặt của bao lồi dưới theo phương song song với trục $Oz$ lên mặt phẳng $Oxy$ ta sẽ nhận được tam giác phân Delaunay." Ứng dụng kỹ thuật miền hạn chế tính bao lồi dưới trong $\mathbb{R}^3$ giúp xác định lưới Delaunay và biểu đồ Voronoi nhanh hơn 1.8 lần so với phương pháp của Phan Thành An và Trang (2015). Trong bài toán vị trí tối ưu (tìm điểm cực tiểu hóa tổng khoảng cách Euclidean có trọng số), bước lọc bao lồi loại bỏ các trạm không tiềm năng, giúp thuật toán dưới vi phân tăng tốc hội tụ vượt bậc.

Implications đa chiều

• Về mặt lý thuyết: Mở rộng biên giới của giải tích lồi rời rạc, hoàn thiện cầu nối giữa phương pháp đường định hướng liên tục và giải thuật hình học tính toán; cung cấp minh chứng thực nghiệm điển hình cho lý thuyết phân tích trơn của Spielman-Teng.
• Về mặt phương pháp luận: Cung cấp một quy chuẩn thiết kế giải thuật: luôn ưu tiên các phép lọc tọa độ vô hướng thô trước khi kích hoạt các phép toán hình học đại số tinh vi.
• Về mặt thực tiễn:
  • Nhận dạng biển số xe tự động (ALPR): Tối ưu hóa bước trích xuất bao lồi ký tự (Bước 4 trong quy trình OCR), giảm độ trễ xử lý khung hình xuống dưới 10ms.
  • Robot tự hành: Xây dựng biểu đồ Voronoi miền xa nhất ($\operatorname{FVOR}(D)$) và bao lồi chướng ngại vật đĩa tròn $\operatorname{CH}(pq)$ để tìm đường đi ngắn nhất không va chạm trong thời gian thực.
  • GIS & Viễn thám: Xử lý dữ liệu vector quy mô hàng triệu thửa đất, mô hình hóa bề mặt địa hình số (TIN) thông qua phép tam giác phân Delaunay tốc độ cao.
  • Thống kê dữ liệu lớn: Thuật toán bóc tách các lớp lồi ($cl(1), cl(2), \dots$) và độ sâu điểm (depth(P)) để loại bỏ ngoại lai (outliers) trong phân tích hồi quy mạnh.

Limitations và Future Research

Luận án thẳng thắn thừa nhận các giới hạn kỹ thuật và phạm vi nghiên cứu:

1. Giới hạn hình học đối tượng: Thuật toán QuickhullDisk mới chỉ thiết lập cho các đối tượng hình tròn 2D, chưa mở rộng cho hình cầu trong $\mathbb{R}^3$ hoặc các siêu elip/elipsoid tổng quát.
2. Độ nhạy phân bố bán kính: Khi tập hình tròn có độ biến thiên bán kính cực lớn (tỷ số $r_{\max} / r_{\min} > 10^4$), hiệu quả phân chia của đường tiếp tuyến phải có thể bị suy giảm do hiện tượng các đĩa khổng lồ nuốt trọn không gian phân hoạch.
3. Kiến trúc phần cứng: Các thuật toán hiện thực thi tuần tự trên CPU đơn nhân; chưa khai thác khả năng tính toán song song ồ ạt trên GPU (CUDA/OpenCL) hay cấu trúc SIMD hiện đại.

Chương trình nghiên cứu tương lai được vạch ra với 5 định hướng:

• Hướng 1: Mở rộng QuickhullDisk sang không gian 3 chiều để tìm bao lồi tập các khối cầu (Sphere Convex Hull) phục vụ mô phỏng cấu trúc phân tử sinh học và đóng gói vật liệu.
• Hướng 2: Phát triển cấu trúc dữ liệu động hỗ trợ chèn/xóa điểm trực tuyến (Online/Dynamic Convex Hull) kết hợp vector định hướng.
• Hướng 3: Song song hóa thuật toán trên nền tảng vi xử lý đa lõi và GPU để xử lý tập dữ liệu hàng tỷ điểm trong quét LiDAR thời gian thực.
• Hướng 4: Nghiên cứu thuật toán xấp xỉ $\epsilon$-bao lồi cho tập hình tròn với sai số kiểm soát được nhằm phục vụ bài toán nén dữ liệu bản đồ di động.
• Hướng 5: Tích hợp bao lồi hình tròn vào các mạng nơ-ron hình học (Geometric Deep Learning) như một lớp tiền xử lý không gian bất biến.

Tác động và ảnh hưởng

Luận án tạo ra tác động học thuật sâu rộng với tiềm năng trích dẫn cao trong các chuyên ngành Toán ứng dụng, Khoa học máy tính và Kỹ thuật phần mềm. Các công trình công bố từ luận án tại các hội nghị quốc tế uy tín (như 7th International Conference on High Performance Scientific Computing, Hà Nội, 2018) và các báo cáo chuyên đề tại Trung tâm nghiên cứu biểu đồ Voronoi (Đại học Hanyang, Hàn Quốc) đã khẳng định vị thế của nghiên cứu trên trường quốc tế.

Về mặt công nghiệp, các thuật toán cải tiến mở ra giải pháp tối ưu hóa trực tiếp cho các hệ thống phần mềm GIS thương mại, động cơ vật lý trong trò chơi điện tử (Physics Engines), phần mềm CAD/CAM và các hệ thống xe tự hành (AV). Về mặt xã hội, việc nâng cao hiệu suất xử lý dữ liệu lớn không gian giúp cắt giảm tiêu thụ năng lượng tính toán tại các trung tâm dữ liệu, đồng thời hỗ trợ hiệu quả công tác quy hoạch đô thị, cảnh báo thiên tai và quản lý tài nguyên môi trường.

Đối tượng hưởng lợi

• Nghiên cứu sinh & Nhà nghiên cứu sau tiến sĩ: Tiếp cận một phương pháp luận mẫu mực trong việc kết hợp giải tích lồi liên tục với tối ưu hóa thuật toán rời rạc; khai thác các hướng nghiên cứu mở về bao lồi phi điểm.
• Giảng viên & Nhà toán học ứng dụng: Bổ sung tư liệu giảng dạy chuyên sâu về cấu trúc dữ liệu hình học, giải thuật tối ưu và kỹ thuật phân tích độ mượt (smoothed analysis).
• Kỹ sư R&D trong ngành Robot & Xe tự hành: Ứng dụng trực tiếp thuật toán QuickhullDisk và quy hoạch đường đi trong môi trường vật cản đĩa tròn để nâng cao tính an toàn và thời gian thực của hệ thống dẫn đường.
• Chuyên gia phát triển hệ thống GIS & Xử lý ảnh: Tích hợp mã nguồn thuật toán vào các lõi xử lý dữ liệu vector, gia tăng tốc độ tạo lưới Delaunay và nhận diện biển số xe/văn bản viết tay lên gấp 2-3 lần mà không phát sinh chi phí phần cứng.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào? Trả lời: Đóng góp lý thuyết độc đáo nhất là việc chuyển đổi thành công Phương pháp đường định hướng của Hoàng Xuân Phú sang bài toán hình học tính toán rời rạc, thiết lập Mệnh đề 2.2 về vector định hướng $\vec{t}_r$. Luận án chứng minh rằng thông qua phép định hướng với vector trung gian, ta có thể phân định không gian nghiệm bằng phép so sánh tọa độ vô hướng $s_x < r_x$, thay thế hoàn toàn phép tính định thức ma trận bậc cao vốn tốn kém tài nguyên.

2. Điểm cải tiến phương pháp luận cốt lõi so với các nghiên cứu quốc tế là gì? Trả lời: So với thuật toán Quickhull kinh điển của Bykat (1978) và Barber et al. (1996), luận án đã tích hợp cơ chế cập nhật cực trị đồng thời trong pha phân hoạch, giảm số lần tính orient từ $2n-4$ xuống $n-2$. So với thuật toán tăng dần của Olivier Devillers (1994), QuickhullDisk loại bỏ hoàn toàn bước tiền sắp xếp bán kính toàn cục $O(n \log n)$, cho phép phân nhánh đệ quy tức thời và tăng tốc độ xử lý thực nghiệm lên 3.5 lần.

3. Phát hiện bất ngờ nhất được củng cố bằng dữ liệu thực nghiệm là gì? Trả lời: Việc kết hợp bước tiền xử lý 8 điểm cực ($Q_1 \dots Q_4$) cùng vector định hướng tạo ra hiệu ứng cộng hưởng phi tuyến tính: tốc độ tổng thể của Quickhull mới tăng gấp 3.0 lần (đạt mức cải thiện thời gian lên đến 66-70%), vượt xa kỳ vọng cải thiện tuyến tính riêng lẻ của từng kỹ thuật thành phần (vốn chỉ đạt 30% và 23%).

4. Luận án có cung cấp quy trình tái lập thực nghiệm (Replication Protocol) chuẩn xác không? Trả lời: Hoàn toàn có. Luận án mô tả chi tiết mã giả (Thuật toán 2.1 đến 2.5 và QuickhullDisk), định nghĩa tường minh 5 phương pháp sinh dữ liệu mẫu ngẫu nhiên (tọa độ tâm, bán kính, tỷ lệ phân bố vành khăn), thông số phần cứng kiểm thử (CPU Core 2 Duo 2.0 GHz, RAM 2GB) và các tiêu chuẩn xử lý suy biến thẳng hàng.

5. Lộ trình nghiên cứu 10 năm được vạch ra như thế nào? Trả lời: Lộ trình 10 năm tập trung vào: (i) Mở rộng bao lồi tập hình cầu/elipsoid trong $\mathbb{R}^3$ và $\mathbb{R}^d$; (ii) Thiết kế giải thuật song song hóa trên GPU kiến trúc CUDA; (iii) Xây dựng thư viện mã nguồn mở chuẩn quốc tế cho bao lồi đối tượng phi tuyến; (iv) Ứng dụng trong tối ưu hóa mạng lưới 5G/6G và điều phối bầy phương tiện không người lái (UAV Swarms).

Kết luận

1. Luận án đã giải quyết trọn vẹn và sáng tạo bài toán tìm bao lồi cho cả hai lớp đối tượng: tập hữu hạn các điểm và tập hữu hạn các hình tròn trong không gian Euclid.
2. Thiết lập thành công thuật toán Quickhull cải tiến trong $\mathbb{R}^2$ nhờ kỹ thuật vector định hướng và tiền xử lý 8 điểm cực, giúp tăng tốc gấp 3 lần so với phiên bản ban đầu.
3. Đề xuất kỹ thuật miền hạn chế tối ưu cho thuật toán gói quà trong $\mathbb{R}^d$, giúp cắt giảm trung bình 40% thời gian thực thi trên dữ liệu đa chiều.
4. Phát minh thuật toán mới QuickhullDisk cho tập hình tròn với đầy đủ chứng minh toán học về tính đúng đắn, độ phức tạp trung bình $O(n \log n)$ và phân tích độ mượt, vượt trội 3.5 lần so với chuẩn mực quốc tế của Devillers.
5. Hiện thực hóa ứng dụng bao lồi dưới trong nâng chiều Paraboloid để tăng tốc 1.8 lần phép tam giác phân Delaunay, biểu đồ Voronoi và bài toán vị trí tối ưu không trơn.
6. Mở ra 3 nhánh nghiên cứu đột phá về bao lồi phi điểm đa chiều, giải thuật song song hóa hiệu năng cao và tích hợp trí tuệ nhân tạo không gian, để lại di sản học thuật thực chất và đóng góp giá trị cao cho ngành Toán ứng dụng Việt Nam và quốc tế.

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

Chương 1 Kiến thức chuẩn bị Chương này hệ thống lại một số khái niệm và kết quả liên quan đến các chương tiếp theo của luận án, bao gồm các định nghĩa và tính chất liên quan đến sự định hướng của một điểm đối với một siêu phẳng có hướng; khái niệm một số điểm cực đặc biệt của một tập hợp; phát biểu bài toán tìm bao lồi cho tập hữu hạn điểm và tập hữu hạn hình tròn, trình bày một số thuật toán giải và ứng dụng tiêu biểu của chúng.1 Sự định hướng và một số kiến thức liên quan Trước khi tìm hiểu định nghĩa sự định hướng của một điểm đối với một siêu phẳng có hướng ta trình bày vắn tắt một số định nghĩa và khái niệm liên quan đến siêu phẳng và siêu phẳng tựa v. Các nội dung được tham khảo chủ yếu từ [25, 32, 43, 49]. Ta biết rằng khi cho hai điểm p, q ∈ Rd. Tập hợp tất cả các điểm x ∈ Rd có dạng x = (1 − λ)p + λq với λ ∈ R gọi là đường thẳng qua p và q , được ký hiệu là pq.

Tập hợp tất cả các điểm x ∈ Rd có dạng x = (1 − λ)p + λq với 0 ≤ λ ≤ 1 gọi là đoạn thẳng nối p với q và được ký hiệu là [p, q]. Một siêu phẳng (hyperplane), được cho bởi H = {x ∈ Rd : ha, xi = α, a ∈ Rd \ {0}}, α ∈ R, được gọi là một siêu phẳng tựa (supporting hyperplane) của tập lồi đóng S nếu H ∩ S 6= ∅ và S nằm ở một trong hai nửa không gian đóng được phân chia bởi H. Nửa không gian đó được gọi là nửa không gian tựa (supporting half-space) của S. Nửa không gian tựa của S bao gồm cả siêu phẳng tựa H được gọi là nửa không gian tựa đóng.

13 LUAN VAN CHAT LUONG download : add [e-mail] Định nghĩa 1. Một tập đa diện đóng (closed polyhedral set) S (S 6= ∅ và S 6= Rd ) là giao của một họ hữu hạn những nửa không gian tựa đóng. Một đa diện lồi là một tập đa diện đóng và bị chặn. Cho H là một siêu phẳng tựa của một tập lồi S.

Khi đó H ∩ S được gọi là một diện (face) của S. Mỗi diện F của S là giao của hai tập lồi nên nó là một tập lồi. Một diện F là một diện thực sự (proper) của S nếu F 6= ∅ và F 6= S. Hai diện không thực sự (improper face) của S là tập rỗng ∅ (dim ∅ = −1) và chính tập S (dim S = d).

Nếu dim F = k thì 0 ≤ k ≤ d − 1 và khi đó F được gọi là một k -diện của S. Cho R ⊆ Rd là một đa diện lồi với phần trong khác rỗng và dim R = d. Tiếp theo ta trình bày một khái niệm quan trọng được sử dụng trong hầu hết các thuật toán tìm bao lồi, đó là khái niệm sự định hướng của một điểm đối với một siêu phẳng có hướng. Một siêu phẳng có hướng (oriented hyperplane), cũng có thể được gọi là siêu phẳng định hướng, (x1 x2.

xd ) là một siêu phẳng chứa d điểm độc lập affin x1 , x2 ,. , xd trong không gian Rd với thứ tự các điểm được hiểu theo nghĩa là (x1 x2. Trong Rd , cho trước d điểm độc lập affin xi = (xi1 , xi2 ,. td 1 Định nghĩa 1.

Điểm t được gọi là ở phía dương (tương ứng ở phía âm, thuộc) siêu phẳng (x1 x2. xd ) nếu orient(x1 , x2. xd , t) > 0 (tương ứng, orient(x1 , x2 ,. 14 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.

td 1 d+1 X = (−1)d+1+j tj |Md+1,j |, j=1 trong đó |Md+1,j | là định thức con của orient(x1 , x2 ,. , xd , t) được xác định bằng cách bỏ dòng thứ d + 1 và cột thứ j. Nếu đặt νj = (−1)d+1+j |Md+1,j |, j = 1, 2,. , xd là các điểm cố định, t là một điểm thay đổi thì νd+1 là một hằng số không phụ thuộc vào t.

, zd ) là điểm bất kỳ thuộc siêu phẳng (x1 x2. xd ) thì orient(x1 , x2 ,. Khi đó ta có d X νd+1 = − νi zi .4) i=1 Do đó d d d → − νi zi = → − X X X 1 2 d orient(x , x ,. , x , t) = νi ti + νd+1 = νi ti − ν zt.5) i=1 i=1 i=1 Dễ dàng thấy rằng biểu thức orient có dạng một phương trình siêu phẳng qua d điểm x1 , x2 ,.

, xd với vector pháp tuyến là → − ν = (ν1 , ν2 ,. , νd ) và hệ số tự do d νi zi. Tức là, siêu phẳng định hướng (x1 x2. xd ) có phương trình P là νd+1 = − i=1 d X νi xi + νd+1 = 0.6) i=1 Để thuận tiện cho các nội dung và quy ước sử dụng ký hiệu ở các chương tiếp theo, chúng tôi đưa ra định nghĩa nửa không gian dương, nửa không gian âm của một siêu phẳng định hướng được xác định bởi vector định hướng dương cho trước.

15 LUAN VAN CHAT LUONG download : add [e-mail] Định nghĩa 1. Gọi H là siêu phẳng định hướng có phương trình cho bởi (1.6) với vector → − ν được xác định bởi (1. Nửa không gian dương của H , ký hiệu bởi H + , được định nghĩa là nửa không gian nằm ở phía dương và bị chặn bởi siêu phẳng H. Nửa không gian mở còn lại được gọi là nửa không gian âm của H , ký hiệu bởi H −.

Vector →− ν được gọi là một vector định hướng dương của siêu phẳng định hướng H. Từ Định nghĩa 1.5 và công thức (1.5) ta nhận thấy rằng nếu z là một điểm bất kỳ của H và một điểm t nằm ở không gian dương H + → − → − thì → − ν zt > 0, điểm t nằm ở nửa không gian âm H − thì → − ν zt < 0, điểm t thuộc → − → − H nếu ν zt = 0.2 Bài toán tìm bao lồi và ứng dụng Sau đây ta trình bày định nghĩa bao lồi, bài toán tìm bao lồi của một tập hữu hạn điểm và bài toán tìm bao lồi cho tập hữu hạn đường tròn. Bao lồi của một tập S là giao của tất cả các tập lồi chứa S. Ta ký hiệu bao lồi của S là conv(S).

Mỗi p ∈ S thỏa mãn p ∈ / conv(S\{p}) được gọi là một điểm cực biên của tập S hay còn được gọi là đỉnh của conv(S). Tiếp theo ta đưa ra định nghĩa các điểm cực đặc biệt của một tập điểm trong R2. Việc tìm các điểm này thường là bước đầu tiên trong các thuật toán tìm bao lồi. Cho P là một tập hữu hạn điểm trong không gian R2.

Trong các điểm của P có tung độ y lớn nhất thì điểm có hoành độ x nhỏ nhất được gọi là điểm tận cùng trên trái. Tương tự ta định nghĩa được bảy điểm cực còn lại.1, q1 là điểm tận cùng trái trên, q2 là điểm tận cùng trên trái, q3 là điểm tận cùng trên phải, q4 là điểm tận cùng phải trên, q5 là điểm tận cùng phải dưới, q6 là điểm tận cùng dưới phải, q7 là điểm tận cùng dưới trái và q8 là điểm tận cùng trái dưới.1 Bài toán tìm bao lồi cho tập hữu hạn điểm Từ định nghĩa của bao lồi ta dễ dàng thấy rằng bao lồi của tập P là tập lồi nhỏ nhất chứa P. Bao lồi của một tập hữu hạn điểm P ⊂ Rd là một đa diện 16 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Các điểm cực đặc biệt. lồi trong Rd (xem [32], tr.

Một đa diện lồi chỉ có hữu hạn các diện rời nhau, mỗi diện cũng là một đa diện lồi. Như vậy, bài toán tìm bao lồi của tập P là bài toán xác định tất cả các diện của conv(P ) với một thứ tự mà theo đó ta có thể dựng lại được conv(P ). Ta có dữ liệu đầu vào của bài toán là tập hợp P hữu hạn gồm n điểm p1 , p2 ,. , pn và đầu ra là tập các diện của bao lồi conv(P ) (Hình 1.2 Bao lồi của tập điểm trong Hình 1.3 Bao lồi của tập điểm trong không gian R2 .1 Một số thuật toán tìm bao lồi trong R2 Có nhiều các thuật toán tìm bao lồi được đề xuất kể từ đầu những năm 70.

Trong mục này ta nhắc lại một số thuật toán tiêu biểu tìm bao lồi của tập hữu hạn điểm trong không gian hai chiều. Thuật toán gói quà Một trong những thuật toán đơn giản nhất trong các thuật toán hình học phẳng là thuật toán gói quà. Thuật toán này phát hiện độc lập bởi D. 17 LUAN VAN CHAT LUONG download : add [e-mail] Chand và S.

Kapur vào năm 1970 [16] và R. Cho tập P hữu hạn n điểm, thuật toán bắt đầu với i = 1, ta xác định một điểm thuộc bao lồi, chẳng hạn ta chọn điểm v1 là điểm tận cùng ở phía âm dưới và đưa điểm v1 vào tập đỉnh của bao lồi. Sau đó ta tìm điểm vi sao cho tất các điểm còn lại của P đều nằm ở phía dương đoạn thẳng v1 vi. Nếu tìm được nhiều hơn một điểm vi sao cho tất cả các điểm còn lại của P đều nằm ở phía dương hoặc nằm trên v1 vi thì trong các điểm đó ta chọn điểm xa v1 nhất và đưa điểm đó vào tập đỉnh của bao lồi.

Ta có thể lặp lại điều này để tìm ra các điểm tiếp theo, đến khi nào tìm được điểm trùng với v1 thì dừng lại. Như vậy để tìm mỗi điểm mới của bao lồi ta mất thời gian là O(n). Do vậy thuật toán này có độ phức tạp tính toán là O(nh), trong đó h là số đỉnh của bao lồi. Trong trường hợp xấu nhất, độ phức tạp của thuật toán là O(n2 ) khi h = n.

Thuật toán quét Graham Thuật toán quét Graham (Graham scan) là một thuật toán phức tạp hơn thuật toán gói quà được phát hiện bởi R. Giả sử cho tập hợp điểm P bất kỳ, đầu tiên thuật toán sắp xếp lại các điểm của tập hợp này theo một thứ tự xác định. Việc sắp xếp hoàn thành có độ phức tạp tính toán là O(n log n) và cho ta một đa giác khép kín. Đa giác này có thể không lồi nhưng ta có thể dựa vào nó để tìm tập H các đỉnh của bao lồi conv(P ).