BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN KIỀU LINH
BÀI TOÁN TÌM BAO LỒI
LUẬN VĂN THẠC SỸ
Chuyên ngành : TOÁN ỨNG DỤNG
Mã số : 00 00 00
Giáo viên hướng dẫn:
TS. HOÀNG NAM DŨNG
THÁI NGUYÊN, 2012
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Lời cảm ơn
Sau một thời gian cố gắng, nỗ lực học tập và nghiên cứu, đến nay tôi đã hoàn
thành luận văn tốt nghiệp thạc sỹ của mình. Để có được kết quả này, tôi xin
bày tỏ lòng biết ơn sâu sắc và lời cảm ơn chân thành nhất đến thầy tôi, TS.
Hoàng Nam Dũng, người đã định hướng nghiên cứu cho tôi trong suốt thời gian
thực hiện luận văn của mình. Cám ơn thầy đã mang đến cho tôi những bài học
quý báu về phương pháp nghiên cứu khoa học. Đó chính là nền tảng cơ bản,
là những hành trang vô cùng quý giá để tôi có thể tiếp cận được với khoa học
thật sự. Thầy đã dạy cho tôi không chỉ những kiến thức khoa học mà còn cả
những bài học về cuộc sống, về tình người. Xin cảm ơn về tất cả những gì thầy
đã mang đến cho tôi.
Tôi xin gửi lời cảm ơn chân thành tới các thầy cô ở trường Đại học Khoa học,
Đại học Thái Nguyên và các thầy cô ở Viện Toán học đã luôn tận tình giúp đỡ,
theo dõi và động viên cho tôi trong suốt quá trình thực hiện luận văn này.
Xin cám ơn những người thân trong gia đình đã hết sức thông cảm, chia sẻ và
tạo điều kiện tốt nhất cho tôi để tôi có thể học tập, nghiên cứu và hoàn thành
những công việc của mình.
Xin cám ơn tất cả những người bạn thân yêu, những người đã yêu mến, chia
sẻ với tôi những khó khăn vui buồn trong khi tôi thực hiện luận văn này.
2

4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Mở đầu
Bài toán tìm bao lồi là một trong những bài toán đặc biệt quan trọng trong
lĩnh vực hình học tính toán bởi các ứng dụng đa dạng của nó. Chẳng hạn như
nhận dạng mẫu, xử lý hình ảnh, tìm đường đi cho robot, số liệu thống kê, . . . .
Hơn nữa bài toán tìm bao lồi còn được áp dụng để tìm ra các bài toán tính toán
hình học khác như tìm tam giác phân Delaunay, tìm đường kính của một tập
hợp, tìm các lớp lồi của một tập hợp, . . . . Vì các ứng dụng quan trọng của nó
nên nhiều nhà khoa học đã bắt tay vào việc nghiên cứu và đưa ra các thuật toán
tìm bao lồi của một tập hợp. Điển hình như sự phát hiện của Chand và Kapur
vào năm 1970 và Jarvis vào năm 1973 với thuật toán gói quà, Ronald Graham
vào năm 1972 với thuật toán quét Graham, W. Eddy năm 1977 và A.Bykat
năm 1978 với thuật toán Quickhull, Timothy Chan vào năm 1993 với thuật toán
Chan, . . . . Hiện nay có rất nhiều nhà khoa học dựa vào các thuật toán này để
cải tiến và tăng tốc cho chúng nhằm đáp ứng các yêu cầu của cuộc sống hiện
đại như xử lí các vấn đề ở tốc độ cao với số lượng lớn. Xuất phát từ lí do trên
luận văn này đưa ra một một số cải tiến nhằm tăng tốc cho việc tính toán khi
tìm bao lồi của một tập hợp điểm trên mặt phẳng.
Luận văn này gồm bốn chương. Chương 1 phát biểu bài toán tìm bao lồi
và trình bày một số ứng dụng quan trọng của bài toán này trong thực tiễn.
Chương 2 trình bày các thuật toán tìm bao lồi trong không gian hai chiều như
thuật toán gói quà, thuật toán quét Graham, thuật toán Quickhull và thuật
toán Chan. Chương 3 đưa ra thuật toán xóa điểm, là thuật toán dựa vào tính
chất của những điểm cực nằm trong tập các đỉnh của bao lồi, để xóa bớt những
điểm nằm trong đa giác tạo bởi các điểm cực, nhằm mục đích giảm bớt số lượng
các điểm đầu vào cho các thuật toán tìm bao lồi. Đồng thời chương này cũng
trình bày một cải tiến cho thuật toán Quickhull. Chương 4 nêu các kết quả tính
toán của các thuật toán đã được trình bày ở chương 3 như thuật toán xóa điểm,
thuật toán Quickhull và Quickhull cải tiến.

. Những điểm x ∈ R
n
có dạng x =
k

i=1
λ
i
p
i
trong đó p
i
∈ R
n
và 0 ≤ λ
i
≤ 1 với
k

i=1
λ
i
= 1 được gọi là một tổ hợp lồi của
p
1
, p
2
, , p
k
∈ R

Định nghĩa 1.6. Trong mặt phẳng, đa giác tạo bởi các đỉnh của một bao lồi
được gọi là biên của bao lồi đó.
1.1.3 Bài toán tìm bao lồi
Cho một tập hợp P hữu hạn điểm, bài toán tìm bao lồi của P là bài toán tìm
tập hợp H các đỉnh của bao lồi conv(P) của P .
Input: Tập hợp P hữu hạn n điểm p
1
, p
2
, , p
n
.
Output: Tập đỉnh của bao lồi conv(P ), H = {h
1
, h
2
, , h
m
}(hình 1.4).
(a) Input (b) Output
Hình 1.4
1.2 Ứng dụng của bài toán tìm bao lồi
Bài toán tìm bao lồi của một tập hợp hữu hạn điểm có ứng dụng đa dạng
trong nhiều lĩnh vực chẳng hạn như nhận dạng mẫu, xử lý hình ảnh, tìm đường
đi cho robot, số liệu thống kê, . . . . Bài toán tìm bao lồi còn được áp dụng rộng
rãi để tìm ra các bài toán tính toán hình học khác và các bài toán này có rất
nhiều ứng dụng trong thực tế như bài toán tìm tam giác phân Delaunay, bài
toán tìm đường kính của một tập hợp, bài toán tìm các lớp lồi của một tập hợp,
. . . . Sau đây ta sẽ trình bày một số ứng dụng quan trọng của bài toán tìm bao
lồi.

đường ngắn hơn trong hai đường biên trên và biên dưới của bao lồi sẽ không
gặp các chướng ngại vật và đường đi ấy là ngắn nhất (hình 1.7).
Hình 1.7 Đường đi ngắn nhất
11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1.2.3 Hệ thống thông tin địa lý (GIS)
Bài toán tìm bao lồi được ứng dụng trong các mô hình biểu diễn dữ liệu của
hệ thống thông tin địa lý GIS. GIS được thiết kế như một hệ thống chung để
quản lý dữ liệu không gian, nó có rất nhiều ứng dụng trong việc phát triển đô
thị và môi trường tự nhiên như là quy hoạch đô thị, quản lý nhân lực, nông
nghiệp, điều hành hệ thống công ích, lộ trình, nhân khẩu, bản đồ, giám sát vùng
biển, cứu hoả, bệnh tật, . . Các ứng dụng này của GIS được trình bày cụ thể
trong [2].
Trong các mô hình biểu diễn dữ liệu của GIS, chúng ta thường nhắc đến một
khái niệm là feature. Feature là một đối tượng trên bản đồ có hình dạng, vị trí
và các thuộc tính xác định cụ thể. Có ba mô hình dữ liệu trong GIS như mô
hình dữ liệu vector, mô hình dữ liệu raster và mô hình TIN. Bài toán tìm bao
lồi được áp dụng một cách gián tiếp trong các mô hình dữ liệu vector và mô
hình dữ liệu TIN. Dưới đây ta trình bày ứng dụng cụ thể của bài toán tìm bao
lồi trong mô hình dữ liệu vector. Nội dung và các hình vẽ trong phần này trích
từ [10].
Mô hình dữ liệu vector xem các sự vật và hiện tượng là tập các thực thể không
gian cơ sở và tổ hợp của chúng (hình 1.8a). Trong mô hình 2D thì các thực thể
cơ sở bao gồm: điểm (points), đường (lines) và vùng (polygons). Đối tượng điểm
biểu diễn các feature không có miền bao hay độ dài, nhiều khi nó biểu diễn các
feature có kích thước quá nhỏ so với tỷ lệ của bản đồ (hình 1.8b). Đối tượng
đường dùng để biểu diễn các feature có chiều dài xác định nhưng không có miền
bao hay những feature rất hẹp so với tỷ lệ bản đồ (hình 1.8c). Đối tượng vùng
được dùng để biểu diễn các feature có miền bao xác định như ruộng đất, ao, hồ
hay các đơn vị hành chính, . . . (hình 1.8d). Sau đó dựa vào các thuật toán phân

toán các ước lượng thông số trong phân tích hồi quy (regression analysis) hoặc
các số thống kê tóm tắt (brief statistics) chẳng hạn như trung bình và phương
sai mẫu mà kết quả là có thể lấy cả những giá trị không tiêu biểu. Do đó các
giá trị ngoại lai thường hay bị bỏ qua để không gây ra lỗi trong dự đoán. Một
ứng dụng của bao lồi có thể giải quyết được vấn đề này, đó là thuật toán tìm
các lớp lồi của một tập hợp bất kỳ. Với đầu vào là các điểm của một mẫu dữ
liệu ngẫu nhiên, ta có thể sử dụng thuật toán này cho vấn đề xóa lớp lồi đến
khi loại bỏ được các giá trị ngoại lai và giữ lại phần gần với trung tâm của các
quan sát hơn. Sau đây chúng ta đi trình bày thuật toán tìm các lớp lồi của một
tập hợp điểm. Nội dung của phần này tham khảo trong [3].
Giả sử ta có tập P , biên của conv(P ) được gọi là lớp lồi đầu tiên của P, kí
hiệu là cl(1). Nếu chúng ta xóa những điểm nằm trên cl(1) và tìm một bao lồi
mới của những điểm còn lại ta sẽ nhận được lớp lồi thứ hai của P , kí hiệu là
cl(2). Như vậy chúng ta sẽ tìm được lớp lồi thứ i + 1 sau khi loại bỏ những điểm
của lớp lồi thứ i. Đây chính là nội dung của bài toán tìm các lớp lồi của một tập
hợp. Từ đó ta có định nghĩa độ sâu của một điểm trong một tập P như sau.
Định nghĩa 1.7. Độ sâu của một điểm p trong một tập P bằng số lớp lồi được
bỏ đi từ tập P trước khi p bị loại bỏ. Độ sâu của một tập P là độ sâu của điểm
sâu nhất của nó, tức là độ sâu của điểm cuối cùng bị loại bỏ. Độ sâu của tập P
kí hiệu là depth(P ) (hình 1.10).
Trong hình 1.10, p
i
có độ sâu là i với i = 0, 1, 2, 3, 4.
Phương pháp tốt nhất để tìm bao lồi của một tập P gồm n điểm có độ phức
tạp tính toán của thuật toán là O(n log n). Định nghĩa độ phức tạp tính toán
của thuật toán được trình bày cụ thể ở chương 2. Đầu tiên ta loại bỏ các đỉnh
của lớp lồi thứ nhất, sau đó tiếp tục tìm bao lồi của các tập điểm còn lại. Do
đó để tìm được độ sâu depth(P ) của P thì độ phức tạp tính toán của thuật toán
là O(n
2

1.2.5 Tìm đường kính của một tập hợp điểm
Bài toán tìm đường kính của một tập hợp điểm là một bài toán rất quan
trọng trong hình học tính toán và có ứng dụng trong những bài toán phân cụm
(clustering), đây là bài toán làm việc với các nhóm đối tượng tương tự nhau
được trình bày cụ thể ở [17], trang 170. Trước khi trình bày thuật toán của bài
toán tìm đường kính của một tập hợp điểm ta có định nghĩa sau.
Định nghĩa 1.8. Cho một tập S có n điểm, tìm trong tập S một cặp điểm sao
cho khoảng cách (khoảng cách Euclid) giữa chúng là lớn nhất. Nếu có nhiều cặp
điểm như vậy thì ta chọn một cặp trong số đó. Độ dài cạnh nối cặp điểm xa
nhất được gọi là đường kính của tập hợp S và cặp điểm xa nhất đó được gọi là
hai đỉnh của đường kính.
Như vậy bài toán tìm đường kính của một tập hợp là bài toán tìm cặp điểm
xa nhất của tập hợp đó. Phương pháp có thể áp dụng giải bài toán này là ta đi
tìm tất cả các khoảng cách giữa hai điểm bất kỳ của tập S và đường thẳng nối
một trong những cặp điểm có khoảng cách lớn nhất là đường kính của một tập
hợp điểm. Cách làm này có độ phức tạp tính toán là O(n
2
). Tuy nhiên dưới đây
ta sẽ trình bày một phương pháp là ứng dụng của bao lồi với độ phức tạp tính
toán là O(n log n).
Mệnh đề 1.1. Cho tập S gồm n điểm trong mặt phẳng. Hai đỉnh đường kính
của tập S là hai điểm cực biên của S, tức là hai điểm đó phải là hai đỉnh của
Hình 1.10 Độ sâu của một điểm và các lớp lồi của một tập hợp.
15
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình 1.11
bao lồi conv(S).
Chứng minh. Bây giờ ta giả sử rằng một đỉnh của đường kính không phải là
điểm cực biên của S. Gọi (d, a) là cặp điểm xa nhất và giả sử rằng a không phải
là điểm cực biên của S. Khi đó a phải nằm trong tam giác dcb nào đó (tính cả

song song với l
2
thì cặp điểm (p
1
, p
2
) được gọi là
cặp điểm đối cực của S.
Dưới đây ta đưa ra một định lí đã được trình bày và chứng minh ở [17]. Định
lý này đưa ra một ý tưởng quan trọng cho thuật toán tìm cặp điểm xa nhất của
một tập điểm trong mặt phẳng.
Định lý 1.1. ([17], định lý 4.18, trang 17) Cặp điểm xa nhất của một tập S là
một cặp đối cực của S mà có khoảng cách lớn nhất.
16
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Như vậy để tìm cặp điểm xa nhất thì ta phải tìm tất cả các cặp đối cực và
chọn một cặp có khoảng cách lớn nhất. Từ mệnh đề 1.1 và định lý 1.1 thì tất cả
các cặp điểm đối cực phải nằm trên bao lồi của tập S. Do đó đầu tiên ta phải
tìm bao lồi của của tập S, sau đó xác định các cặp đối cực từ các đỉnh của bao
lồi và tìm ra cặp có khoảng cách xa nhất. Thuật toán tìm cặp điểm xa nhất có
thể được trình bày như Algorthm 1.
(a) (b)
Hình 1.12
Ta có sự phân tích độ phức tạp tính toán của Algorithm 1 như sau. Bước
(1) có độ phức tạp là O(n log n). Xét đến bước (2), (a) có độ phức tạp là O(h),
(b) - (d) lặp lại như bước (a) cho mỗi cặp đối cực nên cũng có độ phức tạp là
O(h). Cuối cùng (e) cũng có độ phức tạp là O(h). Vì tập S có n điểm nên bao
lồi conv(S) có nhiều nhất n đỉnh, khi đó trong trường hợp xấu nhất thì bước (2)
có độ phức tạp là O(n). Do đó bài toán tìm đường kính của một tập hợp điểm
có độ phức tạp tính toán là O(n log n).

có khoảng cách lớn nhất và sau đó khi xét tiếp đến các đỉnh tiếp theo thì các khoảng cách
này lại giảm dần. Gọi p
i
là điểm có khoảng cách lớn nhất và l
2
là đường thẳng đi qua p
i
sao cho l
2
song song với l
1
(Nếu có hai điểm giống p
i
thì l
2
đi qua cả hai điểm đó). Rõ ràng
là l
1
và l
2
là các đường thẳng tựa trên cặp điểm đối cực của S (hình 1.12a).
(b) Gán θ

1
bằng góc nhọn tạo bởi l
1
và p
1
p
2

:= p
0
p
i
và d

1
:= p
1
p
i
.
If (d

1
≥ d

1
) then
d
1
:= d

1
và e
1
:= p
0
p
i

d
1
, cạnh tương ứng đặt là e
1
và đánh dấu các điểm p
i
đó).
(c) If (θ

1
≤ θ

1
) then
l
1
:=
p
1
p
2
và l
2
:= đường thẳng qua p
i+1
và song song với l
1
,
else
l

2
được tính tương tự như ở bước trên (hình 1.12b). Gán d
2
:= max{d

2
, d

2
}
và e
2
là cạnh tương ứng với d
2
và ta đánh dấu các đỉnh giống như bước trên.
(d) Tiếp tục gán l
1
, l
2
và thực hiện giống bước (c) tới khi mọi đỉnh của bao lồi được đánh dấu.
Khi đó ta có nhiều nhất h khoảng cách d
1
, d
2
, , d
h
và tương ứng có nhiều nhất h cạnh
e
1
, e

ta nói rằng chúng có định hướng dương nếu theo thứ tự đã sắp xếp chúng tạo
thành hình ngược chiều kim đồng hồ, có định hướng âm nếu chúng tạo thành
hình thuận chiều kim đồng hồ và hướng không nếu chúng thẳng hàng (trong đó
bao gồm cả trường hợp có hai hay nhiều hơn các điểm trùng nhau) (hình 2.1).
Lưu ý rằng sự định hướng phụ thuộc vào thứ tự các điểm được đưa ra. Để xét
hướng của các điểm sắp thứ tự (p, q, r) với p = (p
x
, p
y
), q = (q
x
, q
y
) và r = (r
x
, r
y
)
thì ta có thể sử dụng công thức tính định thức cấp ba như dưới đây. Ta định
nghĩa
Orient(p, q, r) := det

1 p
x
p
y
1 q
x
q
y

y
)
và
−→
pr = (r
x
− p
x
, r
y
− p
y
).
Khi đó ta có
Orient(p, q, r) = det

q
x
− p
x
q
y
− p
y
r
x
− p
x
r
y

p
2
nếu Orient(p
1
, p
2
, p
3
) > 0. Điểm p
3
được gọi là bên phải đoạn thẳng p
1
p
2
nếu Orient(p
1
, p
2
, p
3
) < 0 và điểm p
3
được
gọi là nằm trên đoạn thẳng p
1
p
2
nếu Orient(p
1
, p

trên trái, q
3
là điểm tận cùng bên trên phải, q
4
là điểm tận cùng bên phải trên,
q
5
là điểm tận cùng bên phải dưới, q
6
là điểm tận cùng bên dưới phải, q
7
là điểm
tận cùng bên dưới trái, q
8
là điểm tận cùng bên trái dưới.
Một khái niệm mà ta cũng cần phải làm rõ đó là độ phức tạp tính toán của
thuật toán.
Định nghĩa 2.4. Độ phức tạp tính toán của thuật toán được đo trên số lượng
các phép toán cơ bản như phép cộng, phép trừ, phép nhân, phép chia và phép
21
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
Hình 2.2
so sánh mà nó thực hiện. Với mỗi thuật toán cụ thể số lượng này phụ thuộc vào
cỡ (size) của dữ liệu nhập. Như thế ta có thể xem độ phức tạp tính toán của
một thuật toán là một hàm phụ thuộc vào cỡ của dữ liệu nhập. Nếu cỡ mã hóa
của dữ liệu nhập là n thì độ phức tạp có thể được xem là một hàm theo n.
2.2 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 Chand và
Kapur vào năm 1970 và Jarvis vào năm 1973 [11]. Cho tập P hữu hạn n điểm,

i
và gán H := H ∪ {v
i
}. Ta có thể lặp lại điều
này để tìm ra các điểm tiếp theo (hình 2.3e), đến khi nào tìm được điểm trùng
với v
1
thì dừng lại (hình 2.3f). 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 đó n là số điểm trong tập hợp ban đầu cần tìm bao lồi và 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(n
2
) khi
h = n. Thuật toán gói quà có thể được trình bày như thuật toán 2, thuật toán
này được tham khảo từ [13]. Tuy nhiên thuật toán trong [13] giả thiết không có
ba điểm nào thẳng hàng còn ở đây ta sẽ xét trong trường hợp tổng quát.
22
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(a) (b) (c)
(d) (e) (f)
Hình 2.3 Thuật toán gói quà
Algorithm 2 Thuật toán gói quà
Input: Tập P gồm n điểm p
1
, p
2
, , p
n
, giả sử n ≥ 2.
Output: Tập H gồm các điểm là đỉnh của conv(P ).

.
i := i + 1, v := p.
Until p = v
1
.
2.3 Thuật toán quét Graham
Thuật toán quét Graham 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 Ronald Graham vào năm 1972 [7]. Giả sử cho tập hợp 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ự
23
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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 ). Sau khi các điểm của tập hợp P
được sắp xếp thì việc tìm bao lồi của nó có độ phức tạp tính toán là O(n). Vì
vậy thuật toán quét Graham có độ phức tạp tính toán là O(n log n). Trước tiên
ta trình bày việc so sánh hai góc trong mặt phẳng. Việc so sánh này cần cho
việc sắp xếp các điểm trong thuật toán quét Graham ở mục sau.
2.3.1 So sánh hai góc trong mặt phẳng
Sự so sánh hai góc trong mặt phẳng mà ta nói đến ở đây là sự so sánh hai
góc có hướng. Sau đây ta trình bày định nghĩa và nhận xét về góc có hướng.
Góc có hướng được định nghĩa dựa vào việc quay một tia hay một đoạn thẳng
quanh một điểm trong mặt phẳng. Để khảo sát việc quay này ta cần chọn một
chiều quay, gọi là chiều dương, ngược chiều quay của kim đồng hồ. Khi đó ta có
thể định nghĩa góc có hướng như dưới đây.
Định nghĩa 2.5. Cho hai đoạn thẳng IA và IB. Nếu IC quay theo chiều dương
xuất phát từ IA đến trùng với IB thì ta nói đoạn thẳng IC quay một góc AIB,
ta gọi góc AIB là góc có hướng, kí hiệu là

AIB với cạnh đầu là IA và cạnh cuối

p
3
với trục hoành (hình 2.5).
24
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
(a) xp
1
p
3
> xp
1
p
2
(b) xp
1
p
3
= xp
1
p
2
Hình 2.5 So sánh góc
Nhận xét 2.3. Nếu điểm p
3
nằm bên trái đoạn thẳng nối hai điểm p
1
và p
2
,
tức là Orient(p

p
3
= xp
1
p
2
.
2.3.2 Sắp xếp
Việc sắp xếp các điểm bắt đầu bằng việc tìm điểm tận cùng bên dưới phải,
gọi điểm này là p
1
. Sau khi tìm được p
1
ta sắp xếp các điểm còn lại theo thứ
tự tăng dần của các góc tạo bởi chiều dương của trục hoành và đoạn thẳng nối
p
1
với mỗi điểm đó. Rõ ràng độ lớn của các góc này đều nằm trong nửa đoạn
(o, π] và cách so sánh chúng ta đã nêu ở nhận xét 2.3. Tiếp theo ta xét trường
hợp có hai điểm p
i
, p
j
khác nhau nào đó trong P tạo với p
1
ba điểm thẳng hàng,
tức là Orient(p
1
, p
i

không thuộc bao lồi conv(P ) nên ta sẽ xóa điểm
này đi. Ở hình 2.6 những điểm màu trắng là những điểm bị xóa còn những điểm
màu đen không bị xóa. Các thuật toán 3, 4, 5 và 6 ở dưới đây được chỉnh sửa
từ những thuật toán trong [15].
25
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên