Quickhulldisk: một thuật toán tính bao lồi hiệu quả cho tập hữu hạn các hình tròn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

HOÀNG VĂN ĐẠI

QUICKHULLDISK: MỘT THUẬT TOÁN

TÍNH BAO LỒI HIỆU QUẢ CHO TẬP HỮU HẠN

CÁC HÌNH TRÒN

Chuyên ngành: Toán ứng dụng

Mã số: 8 46 01 12

LUẬN VĂN THẠC SĨ TOÁN HỌC

Cán bộ hướng dẫn khoa học:

1. TS. Nguyễn Kiều Linh

2. TS. Dương Thị Việt An

Thái Nguyên, năm 2021

Mục lục

Danh mục ký hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

Chương 1. Bài toán tìm bao lồi cho tập các hình tròn và ứng dụng 7

1.1. Kiến thức chuẩn bị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.2. Sự định hướng cho các hình tròn trong R

2

. . . . . . . . . . . . . . . . . . . . . . 10

1.3. Một số ứng dụng của bài toán tìm bao lồi cho tập các hình tròn 17

Chương 2. Thuật toán QuickhullDisk . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1. Giới thiệu thuật toán QuickhullDisk . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.1.1. Tìm hai điểm cực biên và hình tròn cực biên tương ứng . . . 21

2.1.2. Xác định các tập con khởi tạo DInit

R

và DInit

L

. . . . . . . . . . . . . 23

2.1.3. Tìm hình tròn dr và các tập P1 và P2 . . . . . . . . . . . . . . . . . . . . . 24

2.1.4. Tìm next(dp) và prev(dq) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2. Sự đúng đắn và độ phức tạp tính toán của thuật toán . . . . . . . . . . 28

Chương 3. Một số kết quả tính toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1. Giới thiệu dữ liệu thử nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2. Một số kết quả tính toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1

Danh mục ký hiệu

conv(D) bao lồi của tập hợp D

∂(conv(D)) biên của bao lồi conv(D)

CH(D) tập các hình tròn cực biên của tập D

pq đoạn thẳng nối p với q

∆(a, b) đường thẳng định hướng đi qua hai điểm a, b

theo hướng từ a tới b

orient(a, b, c) định hướng của bộ ba điểm a, b, c

CH(pq) bao lồi của tập hình tròn xung quanh

đoạn thẳng pq

∆(d, d0

) đường thẳng tựa không âm của cặp hình tròn d, d0

dist(c, ∆) khoảng cách từ điểm c đến đường thẳng ∆

I(Σ) giao các nón trong Σ

FVOR(D) biểu đồ Voronoi miền xa nhất của tập

hình tròn D

MCS hình tròn nhỏ nhất chứa một tập

conv(pq) tập lồi nhỏ nhất chứa đoạn thẳng pq

và một số hình tròn xung quanh đoạn thẳng pq

2

Λ(d, d0

) cạnh bao lồi trên ∂conv(D)

DX

∆ tập cắt cực đại

∆−1 đường thẳng có hướng ngược lại của ∆

DR

∆ tập không dương cực đại đối với

đường thẳng định hướng ∆

DL

∆ tập không âm cực đại đối với

đường thẳng định hướng ∆

DInit

R

tập không dương cực đại mở rộng đối với ∆

DInit

L

tập không dương cực đại mở rộng đối với ∆−1

prev(d) hình tròn cực biên kế trước của d

next(d) hình tròn cực biên kế sau của d

|P| lực lượng của tập P

len(p, td) độ dài của cung ptÙd

3