Tổng quan luận án

Luận án tiến sĩ toán học với đề 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" được nghiên cứu sinh Nguyễn Kiều Linh thực hiện tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội, dưới sự hướng dẫn khoa học của TS. Hoàng Nam Dũng và PGS. Phan Thành An, thuộc chuyên ngành Toán ứng dụng (mã số: 9460112.01), bảo vệ năm 2019. Đề tài nhận được sự hỗ trợ kinh phí từ Quỹ Phát triển Khoa học và Công nghệ Quốc gia (NAFOSTED) trong khuôn khổ Đề tài Nghiên cứu khoa học cơ bản mã số 101.

Tính cấp thiết của luận án xuất phát từ vai trò của bài toán tìm bao lồi như một bài toán nền tảng trong lĩnh vực hình học tính toán. Bài toán tìm bao lồi có phạm vi ứng dụng rộng trong đồ họa máy tính, nhận dạng mẫu, xử lý hình ảnh, tìm đường đi cho robot, hệ thống thông tin địa lý (GIS) và phân tích thống kê. Đồng thời, bao lồi là bước tiền xử lý bắt buộc trong nhiều cấu trúc hình học khác như tam giác phân Delaunay, biểu đồ Voronoi, xác định đường kính tập hợp, phân lớp lồi và giải bài toán vị trí tối ưu. Trước yêu cầu xử lý dữ liệu lớn ở tốc độ cao trong tính toán hiện đại, các thuật toán kinh điển đối với tập điểm cần được cải tiến để giảm bớt số lượng phép toán định hướng và thu hẹp không gian tìm kiếm. Đối với dữ liệu đầu vào là tập các hình tròn, việc xây dựng các thuật toán hiệu quả tương tự như thuật toán Quickhull cho tập điểm vẫn là khoảng trống cần được giải quyết.

Mục tiêu nghiên cứu của luận án được xác định gồm ba nội dung chính:

  1. Đề xuất một số kỹ thuật cải tiến cho thuật toán Quickhull tìm bao lồi trong không gian $\mathbb{R}^2$ và thuật toán gói quà trong không gian $\mathbb{R}^d$ ($d \ge 2$), đồng thời thực hiện các tính toán thực nghiệm để so sánh hiệu quả với các thuật toán hiện có.
  2. Đề xuất thuật toán QuickhullDisk tìm bao lồi cho tập hữu hạn các hình tròn trong $\mathbb{R}^2$; chứng minh tính đúng đắn; đánh giá độ phức tạp tính toán trong trường hợp xấu nhất, trường hợp trung bình và theo nghĩa phân tích làm mịn (smoothed analysis); kiểm chứng qua thử nghiệm số.
  3. Giới thiệu ứng dụng của thuật toán tìm bao lồi tập điểm như bước tiền xử lý cho thuật toán dưới vi phân giải bài toán xác định vị trí tối ưu (tối ưu không trơn); đề xuất kỹ thuật hạn chế tính bao lồi dưới trong $\mathbb{R}^3$ ứng dụng trong xác định tam giác phân Delaunay và biểu đồ Voronoi.

Đối tượng và phạm vi nghiên cứu:

  • Đối tượng nghiên cứu: Tập hữu hạn các điểm trong không gian Euclid hai chiều $\mathbb{R}^2$, ba chiều $\mathbb{R}^3$, số chiều tổng quát $\mathbb{R}^d$ ($d \ge 2$) và tập hữu hạn các hình tròn đóng trong mặt phẳng $\mathbb{R}^2$.
  • Phạm vi nghiên cứu: Các thuật toán hình học tính toán (Quickhull, gói quà, QuickhullDisk, bao lồi dưới), phân tích độ phức tạp lý thuyết và thực nghiệm tính toán trên các bộ dữ liệu mô phỏng từ $10^4$ đến $10^6$ phần tử.

Tổng quan tài liệu và vị trí của luận án

Trong luận án, tác giả đã điểm lại có hệ thống các mốc phát triển của bài toán tìm bao lồi cho tập điểm và tập hình tròn:

  1. Hướng nghiên cứu bài toán tìm bao lồi cho tập điểm:
  • Trong không gian $\mathbb{R}^2$: Thuật toán gói quà (Gift wrapping) được D. Chand và S. Kapur đề xuất năm 1970, R. A. Jarvis công bố năm 1973 với độ phức tạp $O(nh)$, trong đó $h$ là số đỉnh bao lồi (trường hợp xấu nhất $O(n^2)$). R. L. Graham (1972) giới thiệu thuật toán quét Graham scan đạt độ phức tạp $O(n \log n)$. R. Bykat (1978) và Eddy (1977) phát triển thuật toán Quickhull với độ phức tạp trung bình $O(n \log n)$ và xấu nhất $O(n^2)$. F. P. Preparata và S. J. Hong (1977) đề xuất thuật toán chia để trị (divide-and-conquer) $O(n \log n)$. M. Kallay (1984) giới thiệu thuật toán tăng dần (incremental). T. M. Chan (1993, 1996) kết hợp Graham scan và gói quà để tạo ra thuật toán Chan có độ phức tạp $O(n \log h)$.
  • Trong không gian $\mathbb{R}^d$: D. Chand và S. Kapur (1970) khởi xướng thuật toán gói quà trong $\mathbb{R}^d$; B. Bhattacharya (1982) chứng minh độ phức tạp tính toán của thuật toán này là $T(d, n) = O(n\phi_{d-1}) + O(\phi_{d-2}\log\phi_{d-2})$. M. Kallay (1981) đề xuất thuật toán beneath-beyond với độ phức tạp $O(n^{\lfloor d/2 \rfloor + 1})$. C. B. Barber, D. P. Dobkin và H. T. Huhdanpaa (1996) phát triển thuật toán Quickhull cho $\mathbb{R}^d$.
  • Về phương pháp đường định hướng: H. X. Phu (Hoàng Xuân Phú) (1987–1991) phát triển phương pháp đường định hướng (the method of orienting curves) để giải các bài toán điều khiển tối ưu có ràng buộc trạng thái. Ý tưởng này được Phan Thành An (2010) và Phan Thành An cùng Trang (2014) áp dụng để tăng tốc thuật toán tìm bao lồi trong $\mathbb{R}^2$ và thuật toán gói quà trong $\mathbb{R}^3$.
  1. Hướng nghiên cứu bài toán tìm bao lồi cho tập hình tròn:
  • D. Rappaport (1992) đề xuất thuật toán chia để trị tìm bao lồi của tập hình tròn với thời gian $O(n \log n)$, đồng thời chỉ ra các ứng dụng trong tính đường kính đĩa, ô Voronoi xa nhất, miền stabbing và miền giao.
  • D. Olivier (1994) và O. Devillers, M. J. Golin (1998) giới thiệu thuật toán tăng dần với độ phức tạp $O(n \log n)$ dựa trên việc sắp xếp bán kính giảm dần và chứng minh mỗi hình tròn có bán kính nhỏ hơn chỉ đóng góp tối đa một cung vào bao lồi.
  • D. Z. Chen và cộng sự (2000) xây dựng thuật toán song song tìm bao lồi của $n$ hình tròn.
  • D. S. Kim và cộng sự (2001) ứng dụng bao lồi tập hình tròn để giải bài toán tìm đường đi ngắn nhất tránh vật cản hình tròn bằng các phép lọc ellipse và lọc bao lồi.

Khoảng trống nghiên cứu luận án lựa chọn giải quyết: Mặc dù thuật toán Quickhull trong $\mathbb{R}^2$ và thuật toán gói quà trong $\mathbb{R}^d$ đã phổ biến, việc tính toán lặp lại phép toán định hướng ($\text{orient}$) vẫn tạo ra chi phí thời gian đáng kể. Đối với tập hình tròn, chưa có phiên bản thuật toán Quickhull được thiết lập riêng để tận dụng cấu trúc tiếp tuyến trực tiếp. Luận án giải quyết các khoảng trống này bằng việc thiết lập các kỹ thuật giảm phép tính định hướng, áp dụng vector định hướng, phân vùng tiền xử lý 8 điểm cực, đề xuất thuật toán QuickhullDisk và xây dựng kỹ thuật hạn chế cho bài toán bao lồi dưới trong $\mathbb{R}^3$.

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án sử dụng các hệ thống lý thuyết, khái niệm và công cụ giải tích - hình học tính toán sau:

  1. Khung lý thuyết và khái niệm nền tảng:
  • Không gian Euclid $\mathbb{R}^d$, đoạn thẳng $[p, q]$, đường thẳng $pq$.
  • Siêu phẳng tựa $H = {x \in \mathbb{R}^d : \langle a, x \rangle = \alpha}$, nửa không gian tựa đóng, tập đa diện đóng, đa diện lồi, diện ($k$-diện) của tập lồi.
  • Bao lồi $\text{conv}(S)$ là giao của tất cả các tập lồi chứa $S$; tập các điểm cực biên $V_C$ hoặc $\text{CH}(D)$.
  • Sự định hướng của điểm đối với siêu phẳng có hướng: Đại lượng $\text{orient}(x_1, x_2, \dots, x_d, t)$ được xác định bởi định thức ma trận cấp $(d+1)$:

$$\text{orient}(x_1, x_2, \dots, x_d, t) = \begin{vmatrix} x_{11} & x_{12} & \cdots & x_{1d} & 1 \ x_{21} & x_{22} & \cdots & x_{2d} & 1 \ \vdots & \vdots & \ddots & \vdots & \vdots \ x_{d1} & x_{d2} & \cdots & x_{dd} & 1 \ t_1 & t_2 & \cdots & t_d & 1 \end{vmatrix}$$

Biểu thức này tương đương phương trình siêu phẳng $\sum_{i=1}^d \nu_i t_i + \nu_{d+1} = 0$, với $\vec{\nu} = (\nu_1, \nu_2, \dots, \nu_d)$ là vector định hướng dương.

  • Tam giác phân Delaunay $DT(P^*)$ và mối liên hệ chiếu với bao lồi dưới $\text{conv}_L(P)$ trên mặt paraboloid $z = (x-a)^2 + (y-b)^2$.
  • Biểu đồ Voronoi miền xa nhất $\text{FVOR}(D)$, hình tròn nhỏ nhất chứa tập hợp $\text{MSC}$, và đường đi ngắn nhất tránh vật cản.
  1. Phương pháp nghiên cứu thực tế:
  • Phương pháp giải tích và hình học tính toán: Thiết lập các bổ đề, mệnh đề toán học về vị trí tương đối của điểm/hình tròn; chứng minh tính đúng đắn của thuật toán QuickhullDisk; phân tích tiệm cận độ phức tạp thuật toán trong trường hợp xấu nhất, trường hợp trung bình và phân tích làm mịn (smoothed analysis dựa trên mô hình nhiễu Gauss $\mathcal{N}(0, \sigma^2)$ và nhiễu đều).
  • Phương pháp thực nghiệm số (định lượng): Cài đặt toàn bộ các thuật toán bằng ngôn ngữ lập trình C. Môi trường phần cứng kiểm thử chuẩn hóa: máy tính cá nhân vi xử lý Intel Core 2Duo 2 * 2.0 GHz, bộ nhớ trong 2GB RAM.
  1. Nguồn dữ liệu thực nghiệm: Dữ liệu thử nghiệm được tạo ngẫu nhiên theo 5 kiểu cấu trúc hình học (mỗi kiểu gồm 27 bộ dữ liệu với kích thước từ $10.000$ đến $1.000.000$ phần tử):
  • Dữ liệu hai đường tròn (tọa độ nguyên ngẫu nhiên trong hai hình tròn cùng bán kính, khác tâm).
  • Dữ liệu hình tròn rỗng (nằm giữa hai đường tròn/ellipse đồng tâm khác bán kính).
  • Dữ liệu hai đường tròn đồng tâm (60% điểm thuộc miền rỗng, 40% điểm nằm trong hình tròn lớn).
  • Dữ liệu hình vuông (điểm phân bố ngẫu nhiên trong hình vuông).
  • Dữ liệu hình vuông rỗng (điểm nằm trong hình vuông lớn $A$ và ngoài hình vuông đồng tâm nhỏ $B$).
  • Dữ liệu trong hình lập phương và trên mặt cầu đối với không gian $\mathbb{R}^3$.

Nội dung chính theo từng chương

Chương 1: Kiến thức chuẩn bị

Chương 1 hệ thống hóa các định nghĩa, tính chất toán học cơ sở và tổng quan các thuật toán kinh điển cùng ứng dụng của bài toán tìm bao lồi.

  • Nội dung lý thuyết: Trình bày chi tiết định nghĩa về siêu phẳng tựa, nửa không gian dương $H^+$ và âm $H^-$, tập đa diện lồi, diện thực sự và không thực sự, định nghĩa 8 điểm cực đặc biệt trong mặt phẳng ($q_1$: tận cùng trái trên, $q_2$: trên trái, $q_3$: trên phải, $q_4$: phải trên, $q_5$: phải dưới, $q_6$: dưới phải, $q_7$: dưới trái, $q_8$: trái dưới). Trình bày cơ chế tính toán giá trị $\text{orient}$ qua khai triển định thức ma trận.
  • Các thuật toán cơ sở: Mô tả cấu trúc của thuật toán gói quà, quét Graham, Quickhull, Chan trong $\mathbb{R}^2$; thuật toán gói quà, beneath-beyond, Quickhull trong $\mathbb{R}^d$; thuật toán tăng dần của Olivier và chia để trị của Rappaport cho tập hình tròn.
  • Phân tích ứng dụng: Tổng hợp các ứng dụng thực tế gồm nhận dạng biển số xe (cô lập ký tự tại Bước 4 bằng bao lồi), tìm đường đi ngắn nhất của robot giữa các chướng ngại vật, quản lý mô hình dữ liệu vector (điểm, đường, vùng) trong hệ thống GIS, xử lý giá trị ngoại lai trong thống kê qua thuật toán bóc tách các lớp lồi $cl(1), cl(2), \dots$ với độ phức tạp $O(n^2)$, tìm đường kính tập điểm qua các cặp điểm đối cực với thời gian $O(n \log n)$, xây dựng lưới tam giác phân Delaunay thông qua phép chiếu bao lồi dưới $\text{conv}_L(P)$ từ paraboloid $z = (x-q_x)^2 + (y-q_y)^2$, tính biểu đồ Voronoi xa nhất $\text{FVOR}(D)$, bài toán tìm hình tròn nhỏ nhất chứa tập hợp $\text{MSC}$, bài toán gói cáp và bài toán tìm đường đi rộng nhất.

Chương 2: Bài toán tìm bao lồi cho tập điểm

Chương 2 tập trung vào các cải tiến thuật toán tìm bao lồi tập điểm trong $\mathbb{R}^2$ và $\mathbb{R}^d$.

  1. Cải tiến thuật toán Quickhull trong $\mathbb{R}^2$:
  • Xử lý điểm thẳng hàng: Luận án chỉ ra nếu $\text{orient}(p_i, p_{i+1}, p_{i+2}) = 0$ trên danh sách kết quả đã sắp xếp thì điểm $p_{i+1}$ nằm giữa và bị loại bỏ; nếu $\text{orient}(p_{m-1}, p_m, p_1) = 0$ thì loại bỏ $p_m$.
  • Kỹ thuật hạn chế phép tính orient (Thuật toán 2.2): Khi phân loại điểm $p_i$ vào tập $P_1$ hoặc $P_2$, thuật toán gán biến tạm lưu giá trị cực đại $\text{max}/\text{min}$ của $\text{orient}(p, q, p_i)$ để xác định trực tiếp điểm xa nhất $r_1, r_2$. Cơ chế này giảm số phép tính $\text{orient}$ ở bước khởi tạo từ $2n - 4$ xuống $n - 2$, và trong hàm đệ quy $\text{Findhull}(P_k, p, q)$ từ $2|P_k| + |S_2|$ xuống $|P_k|$. Kết quả thực nghiệm cho thấy thời gian tính toán giảm khoảng 30% so với Quickhull ban đầu.
  • Kỹ thuật sử dụng vector định hướng (Thuật toán 2.3): Dựa trên Mệnh đề 2.2, chọn vector định hướng $\vec{t}_r$ song song và cùng hướng với trục $Oy$. Khi $p_x \le r_x \le q_x$, điều kiện $\text{orient}(t, r, s) > 0 \Leftrightarrow s_x < r_x$ và $\text{orient}(t, r, s) < 0 \Leftrightarrow s_x > r_x$. Nhờ đó, việc kiểm tra thuộc nửa mặt phẳng được thay thế bằng phép so sánh tọa độ số thực đơn giản, giảm khoảng 23% thời gian tính toán.
  • Kỹ thuật tiền xử lý và chia nhỏ bài toán (Thuật toán 2.4): Dựa trên 8 điểm cực đặc biệt $q_1, \dots, q_8$, loại bỏ toàn bộ các điểm nằm trong đa giác tạo bởi 8 điểm này. Dữ liệu còn lại được phân vào 4 tập con $S_1, S_2, S_3, S_4$ kèm 4 điểm xa nhất tương ứng $r_1, r_2, r_3, r_4$. Kỹ thuật này giúp giảm khoảng 48% thời gian tính toán.
  • Thuật toán Quickhull mới (Thuật toán 2.5): Tích hợp đồng thời cả 3 kỹ thuật trên, mang lại hiệu quả tăng tốc trung bình gấp khoảng 3 lần so với phiên bản Quickhull ban đầu.
Phiên bản thuật toán Nội dung kỹ thuật áp dụng Mức giảm thời gian / Tăng tốc
Thuật toán 2.2 Tận dụng giá trị $\text{orient}$ tìm điểm xa nhất, tránh tính lặp Giảm ~30% thời gian
Thuật toán 2.3 Sử dụng vector định hướng $\vec{t}_r \parallel Oy$ so sánh hoành độ Giảm ~23% thời gian
Thuật toán 2.4 Tiền xử lý 8 điểm cực, chia bài toán thành 4 tập con Giảm ~48% thời gian
Thuật toán 2.5 (Quickhull mới) Kết hợp cả 3 kỹ thuật cải tiến trên Tăng tốc gấp ~3 lần bản gốc
  1. Cải tiến thuật toán gói quà trong không gian $\mathbb{R}^d$ ($d \ge 2$): Luận án đề xuất kỹ thuật miền hạn chế (bounding region) và miền hạn chế tốt nhất (best bounding region) thông qua phép chiếu hạ chiều lên các siêu phẳng tọa độ $Ox_1 \dots x_d$. Các thử nghiệm trên tập điểm ngẫu nhiên trong $\mathbb{R}^2$ và $\mathbb{R}^3$ cho thấy thời gian thực thi giảm trung bình khoảng 40% so với thuật toán gói quà hiện có.

Chương 3: Bài toán tìm bao lồi cho tập hữu hạn các hình tròn

Chương 3 trình bày việc xây dựng thuật toán QuickhullDisk giải bài toán tìm bao lồi cho tập $D = {d_1, \dots, d_n}$ gồm $n$ hình tròn trong $\mathbb{R}^2$.

  • Khái niệm định hướng cho hình tròn: Xác định vị trí tương đối giữa hình tròn $d(c, r)$ và đường thẳng định hướng $\Delta$, định nghĩa tiếp tuyến phải $l(d, d')$, hình tròn cực biên kế trước $\text{prev}(d)$ và kế sau $\text{next}(d)$.
  • Thuật toán QuickhullDisk: Bắt đầu bằng việc xác định hai hình tròn cực biên đặc biệt $d_p, d_q$, dựng các tiếp tuyến chung ngoài tạo thành hai tập hình tròn $D_1, D_2$. Trong mỗi bước, tìm hình tròn $d_r$ có khoảng cách tiếp tuyến lớn nhất, phân chia tập thành các tập con $P_0, P_1, P_2$ và gọi đệ quy tương tự cơ chế Quickhull.
  • Đánh giá lý thuyết: Luận án chứng minh tính đúng đắn toán học của thuật toán; xác định độ phức tạp trong trường hợp xấu nhất là $O(n^2)$, trường hợp trung bình là $O(n \log n)$, và phân tích cận độ phức tạp theo nghĩa smoothed analysis.
  • Kết quả thực nghiệm: So sánh thời gian thực thi giữa QuickhullDisk và thuật toán tăng dần của O. Devillers / D. Olivier trên các tập dữ liệu hình tròn rỗng và hình vuông rỗng. Thuật toán QuickhullDisk đạt tốc độ nhanh hơn trung bình khoảng 3,5 lần.

Chương 4: Ứng dụng của bài toán tìm bao lồi cho tập điểm

Chương 4 trình bày hai hướng ứng dụng của các thuật toán bao lồi đã nghiên cứu:

  1. Bài toán xác định vị trí tối ưu (bài toán tối ưu không trơn): Luận án áp dụng bài toán tìm bao lồi như một bước tiền xử lý nhằm loại bỏ các điểm không đóng vai trò điểm cực biên trước khi thực thi thuật toán dưới vi phân. Kết quả thực nghiệm số chỉ ra việc tính bao lồi trước giúp giảm số chiều dữ liệu, tăng tốc độ hội tụ của thuật toán tối ưu so với khi không sử dụng tiền xử lý.
  2. Kỹ thuật hạn chế tính bao lồi dưới trong $\mathbb{R}^3$: Ứng dụng xây dựng tam giác phân Delaunay trong mặt phẳng thông qua chiếu bao lồi dưới $\text{conv}_L(P)$ của tập điểm chiếu trên paraboloid $z = (x-q_x)^2 + (y-q_y)^2$. Bằng việc áp dụng kỹ thuật miền hạn chế mới, thuật toán tính bao lồi dưới đạt tốc độ nhanh gấp 1,8 lần so với thuật toán hiệu quả được công bố năm 2015 của Phan Thành An và cộng sự.

Kết quả và những đóng góp mới

Luận án đã đạt được các kết quả và đóng góp khoa học cụ thể sau:

  1. Về mặt lý thuyết:
  • Thiết lập cơ sở toán học cho việc sử dụng vector định hướng trong thuật toán Quickhull 2D; chứng minh Mệnh đề 2.2 cho phép thay thế phép tính $\text{orient}$ bằng các phép so sánh tọa độ số thực.
  • Xây dựng hoàn chỉnh thuật toán mới QuickhullDisk cho bài toán tìm bao lồi tập hữu hạn hình tròn trong mặt phẳng $\mathbb{R}^2$; chứng minh tính đúng đắn và xác lập các đánh giá độ phức tạp tính toán (trường hợp xấu nhất $O(n^2)$, trung bình $O(n \log n)$ và theo nghĩa smoothed analysis).
  • Phát triển kỹ thuật miền hạn chế tốt nhất trên các siêu phẳng chiếu tọa độ cho thuật toán gói quà trong $\mathbb{R}^d$ và thuật toán tính bao lồi dưới trong $\mathbb{R}^3$.
  1. Về mặt thực nghiệm và ứng dụng:
  • Thuật toán Quickhull cải tiến kết hợp 3 kỹ thuật (Thuật toán 2.5) tăng tốc độ thực thi trung bình gấp khoảng 3 lần so với phiên bản Quickhull ban đầu trên các bộ dữ liệu thử nghiệm từ $10^4$ đến $10^6$ điểm.
  • Thuật toán gói quà cải tiến trong $\mathbb{R}^d$ giảm trung bình 40% thời gian chạy trong $\mathbb{R}^2$ và $\mathbb{R}^3$.
  • Thuật toán QuickhullDisk đạt tốc độ chạy nhanh gấp khoảng 3,5 lần so với thuật toán tăng dần của O. Devillers.
  • Bước tiền xử lý bao lồi nâng cao hiệu năng giải bài toán xác định vị trí tối ưu không trơn; kỹ thuật hạn chế tính bao lồi dưới trong $\mathbb{R}^3$ tăng tốc gấp 1,8 lần thuật toán tương ứng công bố năm 2015 phục vụ xây dựng lưới tam giác phân Delaunay và biểu đồ Voronoi.

Hạn chế và hướng nghiên cứu tiếp

Dựa trên nội dung và phạm vi nghiên cứu được trình bày trong luận án, các hạn chế và hướng phát triển tiếp theo gồm:

  • Hạn chế:
    • Thuật toán QuickhullDisk mới chỉ được xây dựng và chứng minh trong không gian hai chiều $\mathbb{R}^2$ cho đối tượng hình tròn, chưa mở rộng cho các hình elip hoặc vật thể lồi tổng quát.
    • Các thử nghiệm số chủ yếu thực hiện trên dữ liệu mô phỏng ngẫu nhiên theo các phân bố hình học xác định trên máy tính cá nhân cấu hình đơn nhân Core 2Duo, chưa đánh giá trên các hệ thống tính toán phân tán.
  • Hướng nghiên cứu tiếp:
    • Mở rộng thuật toán QuickhullDisk sang không gian ba chiều $\mathbb{R}^3$ đối với tập các hình cầu hoặc siêu cầu trong $\mathbb{R}^d$.
    • Nghiên cứu song song hóa các thuật toán Quickhull cải tiến và QuickhullDisk trên các kiến trúc tính toán song song, đa luồng hoặc GPU để xử lý dữ liệu quy mô cực lớn.
    • Ứng dụng thuật toán vào các bài toán thực tế quy mô lớn trong hệ thống GIS quốc gia và hệ thống dẫn đường robot tự hành tránh vật cản động.

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với các nhóm đối tượng:

  • Nghiên cứu sinh, học viên cao học và sinh viên ngành Toán ứng dụng, Khoa học máy tính, Toán - Tin: Tài liệu tham khảo về phương pháp phân tích độ phức tạp thuật toán (đặc biệt là smoothed analysis), kỹ thuật tối ưu hóa phép toán định hướng và các cấu trúc hình học lồi.
  • Giảng viên đại học: Sử dụng làm tài liệu giảng dạy chuyên đề Hình học tính toán, Lý thuyết tối ưu, Thuật toán nâng cao và Cấu trúc dữ liệu.
  • Kỹ sư công nghệ và lập trình viên: Tham khảo mã giả chi tiết (từ Thuật toán 2.1 đến Thuật toán 2.5, QuickhullDisk) để cài đặt các mô-đun xử lý dữ liệu không gian trong GIS, nhận dạng ảnh, mô phỏng đồ họa và định tuyến robot.

Câu hỏi thường gặp

1. Kỹ thuật sử dụng vector định hướng trong Chương 2 giúp giảm số phép tính orient như thế nào?
Trong mỗi bước lặp, khi xét bộ ba điểm $(p, q, r)$ với $r$ là điểm xa nhất, thuật toán chọn một vector định hướng $\vec{t}_r$ song song cùng chiều với trục $Oy$. Theo Mệnh đề 2.2, khi $p_x \le r_x \le q_x$, các điểm $s$ có $s_x < r_x$ chắc chắn không nằm về phía âm của vector định hướng, do đó chỉ cần kiểm tra trực tiếp $\text{orient}(p, r, s) > 0$ cho các điểm thỏa mãn $s_x < r_x$. Nhờ phép so sánh hoành độ đơn giản này, thuật toán loại bỏ được một lượng lớn phép tính $\text{orient}$ phức tạp, giúp giảm khoảng 23% thời gian chạy.

2. Bước tiền xử lý tám điểm cực đặc biệt trong Thuật toán 2.4 hoạt động ra sao?
Thuật toán tìm kiếm 8 điểm cực trên biên của tập dữ liệu gồm $q_1, \dots, q_8$ (các điểm tận cùng trên, dưới, trái, phải). Mọi điểm nằm bên trong đa giác tạo bởi 8 điểm cực này chắc chắn không phải là đỉnh của bao lồi và bị loại bỏ ngay từ đầu. Dữ liệu biên còn lại được chia vào 4 tập con $Q_1, Q_2, Q_3, Q_4$ (tương ứng với 4 góc phần tư) để tìm 4 tập $S_1, S_2, S_3, S_4$ độc lập, giúp giảm khoảng 48% thời gian tính toán.

3. Thuật toán QuickhullDisk trong Chương 3 đạt độ phức tạp bao nhiêu và hiệu năng thực nghiệm ra sao?
Thuật toán QuickhullDisk có độ phức tạp tính toán trong trường hợp xấu nhất là $O(n^2)$, trong trường hợp trung bình là $O(n \log n)$, và được chặn trên theo phân tích làm mịn (smoothed analysis). Khi kiểm thử thực nghiệm trên các bộ dữ liệu hình tròn rỗng và hình vuông rỗng, QuickhullDisk có thời gian chạy nhanh hơn trung bình khoảng 3,5 lần so với thuật toán tăng dần của O. Devillers / D. Olivier.

4. Mối liên hệ toán học giữa bao lồi dưới trong $\mathbb{R}^3$ và tam giác phân Delaunay trong $\mathbb{R}^2$ là gì?
Khi chiếu một tập điểm $P^* \subset \mathbb{R}^2$ lên mặt paraboloid $z = (x - q_x)^2 + (y - q_y)^2$ (với $q$ là điểm trung bình), ta thu được tập điểm $P \subset \mathbb{R}^3$. Tam giác phân Delaunay $DT(P^*)$ trên mặt phẳng chính là hình chiếu vuông góc của các mặt thuộc bao lồi dưới $\text{conv}_L(P)$ xuống mặt phẳng $Oxy$. Do đó, việc tối ưu hóa thuật toán tính bao lồi dưới trong $\mathbb{R}^3$ sẽ trực tiếp tăng tốc độ xây dựng lưới Delaunay và biểu đồ Voronoi.

5. Luận án đã xử lý trường hợp các điểm thẳng hàng trong thuật toán Quickhull như thế nào?
Để không phải giả thiết các điểm ở vị trí tổng quát, sau khi thu được danh sách các điểm cực sắp thứ tự $p_1, p_2, \dots, p_m$, thuật toán kiểm tra nếu $\text{orient}(p_i, p_{i+1}, p_{i+2}) = 0$ ($i = 1, \dots, m-2$) thì xóa bỏ điểm nằm giữa $p_{i+1}$; nếu $\text{orient}(p_{m-1}, p_m, p_1) = 0$ thì xóa điểm cuối cùng $p_m$.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Kiều Linh đã giải quyết trọn vẹn các mục tiêu nghiên cứu đề ra trong lĩnh vực hình học tính toán và toán ứng dụng. Tác giả đã đề xuất thành công các kỹ thuật tối ưu hóa phép toán định hướng và tiền xử lý phân vùng cho thuật toán Quickhull trong $\mathbb{R}^2$, phát triển kỹ thuật miền hạn chế cho thuật toán gói quà trong $\mathbb{R}^d$, đồng thời xây dựng thuật toán QuickhullDisk mới cho tập hình tròn trong mặt phẳng với đầy đủ chứng minh đúng đắn và đánh giá độ phức tạp. Các kết quả thực nghiệm số nhất quán với phân tích lý thuyết, khẳng định sự vượt trội về tốc độ tính toán của các thuật toán đề xuất và mở ra khả năng ứng dụng hiệu quả trong tối ưu không trơn, xây dựng lưới Delaunay và xử lý dữ liệu không gian.