Tập lồi, bao lồi
Định nghĩa 1.1 (xem [14]) Một tập E 3 được gọi là tập lồi nếu với mọi x 1 , x 2 thì đoạn thẳng x 1 , x 2
Hình 1 cho ví dụ về tập lồi và tập không lồi
Ví dụ 1.2 Các hình tam giác, hình tròn trong mặt phẳng; các nửa không gian là các tập lồi
Nhận xét 1.3 Giao của một họ bất kỳ các tập lồi là tập lồi, tuy nhiên hợp của một họ các tập lồi chưa chắc đã là tập lồi x 1 2 x
Hình 1 Tập A lồi, tập B không lồi x 1 x 2
Định nghĩa 1.4 (xem [3]) Một tổ hợp lồi của x 1 , x 2 , , x k E 3 là một tổng có dạng
M ệnh đề 1.5 (xem [3]) Giả sử E 3 là tập lồi và x 1 , x 2 , , x m Khi đó, với mọi i R, i 0 i 1 , m sao cho 1
Chúng tôi chứng minh bằng phương pháp quy nạp
Nếu m 2, với 1 , 2 0, 1 , 2 R, 1 2 1; x 1 , x 2 , theo Định nghĩa 1.1, chúng ta luôn có 1 x 1 2 x 2 Giả sử mệnh đề đúng với m k ,
k , chúng ta cần chứng minh mệnh đề đúng với m k 1, nghĩa là, với
Không mất tính tổng quát, giả sử 0 k 1 1 (vì nếu k 1 1 thì từ 1
i 1 , k 1 suy ra 1 2 k 0 , do đó x x k 1 ) Khi đó, chúng ta có 1 k 1 1 k 0 Suy ra 0
nên theo giả thiết quy nạp, chúng tôi đặt
Vậy với y , x k 1 , 1 k 1 0 và ( 1 k 1 ) k 1 1, chúng ta có
1 k 1 y k 1 x k 1 x □ Định nghĩa 1.6 (xem [14]) Cho tập E 3 Khi đó, giao của tất cả các tập lồi chứa gọi là bao lồi của , kí hiệu là conv
(i) conv là tập lồi nhỏ nhất chứa
(ii) là tập lồi khi và chỉ khi conv Định lý 1.8 (Định lý Caratheodory trong E 3 ) (xem [3])
Bao lồi của tập E 3 là tập tất cả các tổ hợp lồi của không quá bốn điểm của
Bao lồi của một tập hợp hữu hạn điểm \( A \) trong không gian \( E^2 \) là một hình đa giác lồi, với các đỉnh của đa giác này chính là các điểm cực biên của tập hợp conv \( A \), và chỉ có những điểm cực biên đó.
Bao lồi của một tập hợp hữu hạn điểm trong không gian E³ là một hình đa diện lồi Các mặt của hình đa diện này có các đỉnh thuộc tập hợp và chỉ bao gồm các mặt cực biên của tập hợp conv .
Nhận xét 1.11 (xem [11]) Một khối đa diện lồi được mô tả bằng biên gồm các mặt, các cạnh và các đỉnh.
Điểm cực biên, cạnh cực biên
Định nghĩa 1.12 (xem [8]) Cho tập lồi E 3 , điểm x được gọi là điểm cực biên của tập nếu x a , b ; với mọi a, b thì x a hoặc x b (xem hình 2) a x b
Hình 2 x là điểm cực biên của tập
Trong E 2, nếu A là một đoạn thẳng hoặc một hình tam giác, thì các điểm cực biên của nó tương ứng với hai đầu mút của đoạn thẳng và các đỉnh của hình tam giác.
Nếu là một hình hộp chữ nhật hoặc hình tứ diện, các điểm cực biên tương ứng là các đỉnh của chúng Tuy nhiên, tập hợp các điểm cực biên của một tập lồi không phải lúc nào cũng hữu hạn; ví dụ, trong trường hợp hình cầu, mọi điểm trên biên đều là điểm cực biên Định nghĩa 1.14: Một đoạn [a, b] được gọi là cạnh cực biên của khối đa diện lồi conv nếu tồn tại một mặt phẳng đi qua đường thẳng ab, sao cho mọi điểm của nằm về một phía của mặt phẳng đó Định nghĩa 1.15: Mặt phẳng F được gọi là mặt cực biên của conv nếu conv nằm hoàn toàn ở một phía của mặt phẳng F, trong khi phía còn lại hoàn toàn rỗng.
Các điểm trong của bao lồi không được xem là điểm cực biên Một điểm được coi là điểm cực biên của bao lồi nếu có một đường thẳng đi qua điểm đó mà không cắt bao lồi ngoài điểm đó.
(iii) Một mặt F là mặt cực biên của conv nếu tồn tại một mặt phẳng
chứa F mà ngoài mặt F thì không cắt conv Định nghĩa 1.17 (xem [6]) Trong mặt phẳng Oyz , cho ba điểm
Trong không gian 3 - chiều, nhìn mặt phẳng Oyz từ phía x và nhìn trục
Oy từ phải sang trái, gọi t là điểm nằm bên trái (tương ứng, nằm trên, nằm bên phải) của đường thẳng có hướng pq từ p đến q nếu S 0 (tương ứng,
Quy ước 1.18 Để cho đơn giản, chúng tôi quy ước phía bên trái cạnh định hướng là phần bên trong của tập
Thủ tục xác định cạnh cực biên của bao lồi trong mặt phẳng
(Trong không có ba điểm nào thẳng hàng, …)
Tìm: Các cạnh cực biện của bao lồi conv
Mô tả thủ tục (xem [10])
Cạnh cực biên được xác định thông qua các điểm cực biên, cho phép chúng ta tìm ra cạnh cực biên từ những điểm này Theo định nghĩa, nếu đoạn thẳng [a, b] là cạnh cực biên của tập hợp conv A, thì mọi điểm trong A sẽ nằm về một phía của đường thẳng đi qua [a, b] Thủ tục xác định cạnh cực biên có thể được mô tả như sau.
- Lấy hai điểm p i , p j tuỳ ý thuộc hệ điểm p 0 , p 1 , , p n 1 E 2 đã cho
+ Nếu tất cả các điểm p l nằm bên trái hoặc nằm trên [ p i , p j ] thì
[ p i p j là một cạnh cực biên của conv
+ Nếu có một điểm p l nằm bên phải [ p i , p j ] thì [ p i , p j ] không là cạnh cực biên của conv
Dựa vào hai tính chất này, Thủ tục 1 bên dưới được xây dựng để kiểm tra xem một cạnh có phải là cạnh cực biên của conv hay không
Thủ tục 1: Xác định cạnh cực biên (xem [10])
4 if với mọi p l nằm bên trái (hoặc nằm trên) [ p i , p j ] then
5 [ p i , p j ] là cạnh cực biên của conv
Ví dụ 1.19 Cho p 0 1 ; 2 , p 1 2 ; 8 , p 2 4 ; 17 , p 3 2 ; 20 , p 4 2 ; 13 , p 5 3 ; 13 E 2 Tìm các cạnh cực biên của conv
Dựa vào Thủ tục 1, quá trình tìm cạnh cực biên của conv được thực hiện như sau
Tại điểm p0, chúng ta có các cạnh [p0, p1], [p0, p2], [p0, p3], [p0, p4], và [p0, p5] Khi xem xét vị trí của các điểm p2, p3, p4 và p5 so với [p0, p1], áp dụng công thức (1), tại điểm p2, ta tính được S2 = (2 - 1)(17 - 2)(-4 - 1)(8 - 2) = -3 < 0 Điều này cho thấy p2 nằm bên phải của [p0, p1], do đó, [p0, p1] không phải là cạnh cực biên của tập hợp convA.
+ Xét vị trí các điểm p 1 , p 3 , p 4 , p 5 với [ p 0 , p 2 ] Tương tự, chúng tôi kết luận được p 1 , p 3 , p 4 , p 5 nằm bên trái [ p 0 , p 2 ] Vậy [ p 0 , p 2 ] là cạnh cực biên của conv
+ Xét vị trí các điểm p 1 , p 2 , p 4 , p 5 với [ p 0 , p 3 ] Tương tự, chúng tôi kết luận được p 1 , p 2 nằm bên phải [ p 0 , p 3 ] Vậy [ p 0 , p 3 ] không là cạnh cực biên của conv
+ Xét vị trí các điểm p 1 , p 2 , p 3 , p 5 với [ p 0 , p 4 ] Tương tự, chúng tôi kết luận được p 1 , p 2 , p 3 nằm bên phải [ p 0 , p 4 ] Vậy [ p 0 , p 4 ] không là cạnh cực biên của conv
+ Xét vị trí các điểm p 1 , p 2 , p 3 , p 4 với [ p 0 , p 5 ] Tương tự, chúng tôi kết luận được p 1 , p 2 , p 3 , p 4 nằm bên phải [ p 0 , p 5 ] Vậy [ p 0 , p 5 ] không là cạnh cực biên của conv
Do đó, [ p 0 , p 2 ] là cạnh cực biên của conv
- Tương tự, tại các điểm p 1 , p 2 , p 3 , p 4 , p 5 , chúng tôi kết luận được [ p 2 , p 3 ],
[ p 3 p 5 , [ p 5 , p 0 ] là các cạnh cực biên tiếp theo của conv
Vậy các cạnh cực biên của conv là [ p 0 , p 2 ], [ p 2 , p 3 ], [ p 3 , p 5 ], [ p 5 , p 0 ]
Hình 3 Hình minh hoạ cho ví dụ 1.19 p 3 p 2
Đường thẳng và mặt phẳng trong E 3
Gỉả sử, mặt phẳng đi qua ba điểm độc lập p p x , p y , p z ,
q x q y q z q , , và t t x , t y , t z Như chúng ta đã biết, phương trình mặt phẳng có dạng
yn zn d xn x y z ở đây, n n x , n y , n z là vectơ pháp tuyến của mặt phẳng (xem hình 4) Rõ ràng d : n x q x n y q y n z q z Với w w x , w y , w z và n z 0 đặt z y y x x z n w n w n w d
: thì w : w x , w y , w z Khi đó, nếu w z w z (tương ứng,
Trong không gian ba chiều, nếu điểm z nằm phía trên mặt phẳng R, thì nó được ký hiệu là w Đường thẳng pq, tương ứng với đoạn thẳng [p, q], được định nghĩa là đường thẳng có hướng đi từ điểm p đến điểm q.
Hình 4 n n x , n y , n z là vectơ pháp tuyến của mặt phẳng p
Khi đó, V 0 khi và chỉ khi p , q , t tạo thành một vòng quay ngược chiều kim đồng hồ khi nhìn từ phía w (xem [10]) (3)
Trong tình huống này, chúng ta xem xét w nằm phía dương của mặt phẳng đi qua ba điểm p, q, t (hình 5), với điều kiện ba điểm này tạo thành một vòng quay ngược chiều kim đồng hồ khi nhìn từ phía w Chúng tôi ký hiệu mặt phẳng này là f(p, q, t).
Cho là tập hữu hạn điểm trong E 3, bao lồi conv của tập này là một khối đa diện lồi Một khối đa diện lồi được mô tả bằng biên gồm các mặt, các cạnh và các đỉnh Nếu không có bốn điểm nào của đồng phẳng, mọi mặt của conv sẽ là các tam giác Gọi f là một mặt tam giác của conv với ba đỉnh p, q, t, mặt f có một sự định hướng, trong đó conv nằm ở một phía của mặt phẳng chứa f, và phía còn lại hoàn toàn rỗng Giả sử V > 0 với mọi w thuộc \ {p, q, t} Chúng tôi ký hiệu mặt f bằng f(p, q, t) hoặc f(e, t), với e được định nghĩa là đoạn thẳng [p, q].
Để xác định xem ba điểm p, q, t có tạo thành một mặt của conv(ℝ) hay không, chúng ta sẽ kiểm tra xem điểm w có nằm ở phía dương của mặt f(p, q, t) hay không Điều này được thực hiện bằng cách xác định rằng V > 0 với mọi w thuộc ℝ mà không phải là p, q, t.
Hình 5 w nằm phía dương của mặt f p , q , t f w p q t e
Trong bài viết này, chúng tôi sẽ không đề cập đến các vấn đề liên quan đến sự suy biến, chẳng hạn như các điểm có tọa độ x, y trùng nhau, ba điểm thẳng hàng hoặc bốn điểm đồng phẳng.
max : x max x : x , y , z , x min : min x : x , y , z , y max : max y : x , y , z ,
Trong bài viết này, chúng ta xem xét một tập hợp điểm \( \mathcal{R} \) với các tọa độ \( (x, y, z) \) thuộc không gian thực Để xác định các giá trị tối thiểu và tối đa của \( y \) và \( z \), ta có \( y_{\text{min}} = \min\{ y : (x, y, z) \in \mathbb{R} \} \), \( z_{\text{max}} = \max\{ z : (x, y, z) \in \mathbb{R} \} \), và \( z_{\text{min}} = \min\{ z : (x, y, z) \in \mathbb{R} \} \) Hình chiếu của \( \mathcal{R} \) trên mặt phẳng Oyz được biểu diễn bởi \( \mathcal{R}' = \{ p_0', p_1', \ldots, p_{n-1}' \} \) với \( p_i' = (0, y_i, z_i) \) Tập hợp \( \mathcal{R} \) nằm trong một hình hộp chữ nhật có các mặt giới hạn bởi \( x = x_{\text{max}} \), \( x = x_{\text{min}} \), \( y = y_{\text{max}} \), \( y = y_{\text{min}} \), \( z = z_{\text{max}} \), và \( z = z_{\text{min}} \) Do đó, ta có \( \text{conv}(\mathcal{R}) \subseteq \{ (x, y, z) : x_{\text{min}} \leq x \leq x_{\text{max}}; y_{\text{min}} \leq y \leq y_{\text{max}}; z_{\text{min}} \leq z \leq z_{\text{max}} \} \).
Giả sử mn n m là một mặt của hình hộp chữ nhật, với n, m là giao của mặt x max x và mặt z z min , n, m là giao của mặt x x max và mặt z z max Vì
nên nằm trong mặt phẳng Oyz
Trong không gian ba chiều, chúng tôi quan sát mặt phẳng Oyz từ phía x và trục Oy từ phải sang trái Chúng tôi chọn các điểm p 0 , p 1 , p n 1 thuộc tập hợp trên mặt phẳng Oyz, và xác định điểm thấp nhất bên phải của , được đặt là p 0 Tiếp theo, chúng tôi lấy điểm p 1 .
Hình 6 Biểu diễn vị trí của các điểm p 0 , p 1 , p n 1 trong mặt Oyz
ứng, p n 1 ) sao cho các điểm khác của ở bên trái của p 0 p 1 (tương ứng,
(xem hình 6) Vì p 0 , p 1 (tương ứng, p 0 , p n 1 ) là cạnh của bao lồi conv, khi đó, nếu p 0 x 0 p 0 x thì p i i 2 nằm phía dương của mặt f p 0 , p 1 , p 0 ; nếu x x p p 0 0 0 thì p i i 2 nằm phía dương của mặt f p 0 , p 0 , p 1
M ệnh đề 1.20 (xem [10]) Giả sử { p i x i , y i , z i E 3 , i 0 , 1 , , n 1 } ,
n Trong mặt phẳng Oyz , các điểm p 0 , p 1 , p n 1 được xác định bởi (4) Khi đó, p 0 , p 1 và p 0 , p n 1 là các cạnh của conv
Trong luận văn này, chúng tôi sử dụng p 0 , p 1 được xác định bởi (4) là cạnh đầu tiên của bao lồi conv trong các thuật toán
Mệnh đề 1.21 cho rằng trong không gian E3, tập hợp các điểm được định nghĩa bởi các tọa độ p i = (x i, y i, z i) với i từ 0 đến n - 1, trong đó n ≥ 4 Ba điểm a, b, p là các điểm phân biệt trong , và chúng cắt các mặt phẳng mn và mn tương ứng tại các điểm u và u Các hình chiếu tương ứng của a, b, p lên mặt phẳng Oyz theo phương song song với trục Ox được ký hiệu là a', b', p', u p và u p.
Oyz , các điểm a , b , p nằm cùng phía với đường thẳng định hướng u p u p (có thể nằm trên đường thẳng u p u p )
Gọi là mặt phẳng chứa đường thẳng u u, với : a , b , p Đường thẳng u u là giao điểm của mặt x x max trong hình hộp chữ nhật có các mặt xung quanh là x x max, x x min, y y max, y y min, z z max, z z min Hình chữ nhật mn n m được xác định bởi tập x max , y , z : y min y y max ; z min z z max , cho thấy m n mn song song với Oyz Hơn nữa, a , b , p giao với mn n m tại u u, cho thấy a , b , p nằm cùng phía với đường thẳng u u Do đó, ta có p b a , , nằm cùng phía với đường thẳng u p u p.
Chú ý, nếu a , b , p vuông góc với mn n m thì a , b , p u p , u p
Trong không gian 3 - chiều, hình hộp chữ nhật chứa tất cả các điểm của
Trong trường hợp đặc biệt, hình hộp chữ nhật với các mặt xung quanh là x = x max, x = x min, y = y max, y = y min, z = z max, z = z min được coi là biên của conv Giả sử conv được xác định trong thuật toán gói quà, với cạnh đầu tiên [p0, p1] được xác định trong (4), một miền hạn chế sẽ được xác định trong biên.
Thuật toán gói quà tìm bao lồi của tập hữu hạn điểm trong không
Năm 1970, D R Chand và S S Kapur đã đưa ra thuật toán gói quà tìm bao lồi của tập hữu hạn điểm trong không gian 3 - chiều (xem [11]) Cơ sở
Hình 7 Mặt a , b , p cắt hình chữ nhật mn n m tại u u p a
Ý tưởng bắt đầu từ một cạnh cực biên của bao lồi, tìm mặt đầu tiên chứa cạnh này và sau đó xác định các mặt liền kề Quá trình này tiếp tục cho đến khi tất cả các mặt bao quanh tập hợp điểm được xác định Chúng ta giả định rằng khối đa diện là đơn hình, nghĩa là mỗi mặt của nó chứa chính xác ba cạnh Theo định lý, trong một khối đa diện đơn hình, một cạnh e của bao lồi là giao của hai mặt F1 và F2, và hai mặt này có chung cạnh e khi và chỉ khi e được xác định bởi hai đỉnh thuộc cả F1 và F2.
Định lý 1.23 là nền tảng cho Thuật toán 1, trong đó cạnh e của mặt F1 được sử dụng để tạo ra mặt liền kề F2, có chung cạnh e với F1.
Tìm: Q là tập tất cả các mặt của conv
Hình 8 Hai mặt F 1 , F 2 được gọi là liền kề e
Mô tả thuật toán (xem [11])
Tìm cạnh cực biên đầu tiên e của conv
Chọn hệ trục Oxyz Chiếu các điểm p i x i , y i , z i , i 0 , n 1 theo phương song song với trục Ox xuống mặt phẳng Oyz, chúng ta được tập
Trên mặt phẳng Oyz, chúng ta tiến hành tìm cạnh cực biên đầu tiên của tập hợp , với các điểm được định nghĩa là p i = (0, y i, z i), trong đó i = 0 đến n - 1, bằng cách sử dụng Thủ tục 1 Cạnh này sẽ tương ứng với cạnh cực biên của bao lồi conv, đồng thời cũng là cạnh cực biên của bao lồi conv.
p 0 , p 1 : e là cạnh cực biên của conv, khi đó p 0 , p 1 : e là cạnh cực biên của conv (xem hình 9)
Tìm mặt đầu tiên F 1 chứa cạnh e của conv
Giả sử p 0 , p 1 : e là cạnh cực biên của conv và p 0 , p 1 : e là hình chiếu song song của e xuống mặt phẳng Oyz Gọi l là nửa mặt phẳng bờ e chứa p l thuộc \ p 0 , p 1 Sử dụng mặt phẳng e , e làm chuẩn, ta xét góc giữa mặt phẳng e , e và mặt phẳng l để tìm góc nhỏ nhất Từ đó, xác định điểm cực biên thứ ba, giả sử là p 2, và mặt đầu tiên của conv được ký hiệu là F 1 : p 0 p 1 p 2.
Hình 9 p 0 , p 1 e là cạnh cực biên của conv Khi đó, p 0 , p 1 e là cạnh cực biên của conv
Tìm mặt F 2 liền kề và có chung cạnh e với mặt F 1
Giả sử F1 là tam giác với các đỉnh p0, p1, p2 và đoạn thẳng [p0, p1] được ký hiệu là e Gọi nửa mặt phẳng chứa F1 có bờ e là (α) và nửa mặt phẳng chứa p_i (i thuộc R \ {p0, p1, p2}) có bờ e là (β_i) Để xác định mặt F2 liền kề có chung cạnh e với mặt F1, chúng ta cần tìm góc lớn nhất giữa (α) và (β_i), giả sử góc này được ký hiệu là ρ_k = ∠(α, β_k) Khi đó, F2 được xác định là tam giác với các đỉnh p0, p1, pk.
Tiếp tục quá trình tìm mặt liền kề cho đến khi tìm được conv
Để xác định góc lớn nhất giữa nửa mặt phẳng α và các nửa mặt phẳng βi, cần so sánh cotan của các góc này và chọn góc có cotan lớn nhất Phương pháp tính toán góc giữa mặt phẳng α và nửa mặt phẳng βk là bước quan trọng trong quá trình này.
Giả sử p 0 , p 1 : e , F 1 : p 0 p 1 p 2 , điểm p i Gọi n là vectơ pháp tuyến, đơn vị của và a là vectơ đơn vị của cạnh e và vectơ n
Khi đó, n nằm cùng phía với nửa mặt phẳng chứa p k có bờ ,
Hình 10 là góc tạo bởi ( ) và ( k ) p 0 p 1 p 2 F 1 e
Do đó, a vuông góc với n và a vuông góc với p 1 p 0 Suy ra
Từ p k kẻ p k H vuông góc với Trong kẻ HM song song với
Dựng hình chữ nhật p k HMN Khi đó, k là góc tạo bởi
và k (xem hình 11) Ta có cotan k cotan k
Mặt khác, ta lại có p p k a p M MH Hp k a
Tương tự, ta có MN p p k n
Hình 11 Góc k là góc tạo bởi và k
Với mỗi p k , chúng tôi tính được k cotan n p p a p p k k k
Thuật toán 1: Thuật toán gói quà (xem [11])
2 gọi Thủ tục 1 để tìm mặt F 1 ;
3 gán là tập các cạnh của F 1 ;
6 begin lấy F 1 từ tập Q ; ( Q có cấu trúc hàng đợi)
7 T đặt là tập các cạnh của F 1 ;
9 begin tìm mặt cực biên F 2 liền kề và có chung cạnh e với F 1 ;
10 gán vào tất cả các cạnh của F 2 chưa có trong và xoá tất cả các cạnh của F 2 đã có trong ;
Khi đó, Q là tập có thứ tự các mặt cực biên của conv
Tập được chứa trong hình hộp chữ nhật với các giới hạn: x max = 4, x min = -2, y max = 4, y min = -3, z max = 20, z min = 2 Dựa trên thuật toán gói quà, quá trình tìm bao lồi conv được thực hiện một cách hiệu quả.
2 gọi Thủ tục 1 để tìm mặt đầu tiên F 1 đi qua cạnh e của conv;
Chọn hệ trục toạ độ Oxyz Chiếu các điểm của theo phương song song với trục Ox xuống mặt phẳng Oyz ta được tập
Giả sử e' = [p0', p2'] là cạnh cực biên đầu tiên của conv R' theo Thủ tục 1, thì e = [p0, p2] là cạnh cực biên đầu tiên của conv R Sử dụng mặt phẳng (e, e') làm chuẩn, ta sẽ xem xét góc tạo bởi mặt phẳng này.
Hình 12 (a ) Tập được chứa trong hình hộp chữ nhật (b ) Biểu diễn bao lồi conv y
Gọi n là vectơ pháp tuyến, đơn vị của mặt e , e và a là vectơ đơn vị của cạnh e và n
Theo Nhận xét 1.24, ta có
Khi đó, góc tạo bởi mặt phẳng k chứa p k , với p k \ p 0 , p 2 và mặt phẳng e , e là n p p a p p k k k
2 Do đó, tại các điểm p 1 , p 3 , p 4 , p 5 , chúng tôi có các góc tương ứng là
Vậy mặt p 0 p 2 p 3 : F 1 là mặt đầu tiên của conv
T là tập các cạnh của F 1 ;
(Tương tự với cách tìm F 1 ở trên, chúng tôi tìm được các mặt F 2 phía dưới)
- với e [ p 0 , p 3 ] T p 0 , p 2 , p 0 , p 3 , p 2 , p 3 thì F 2 p 0 p 3 p 4 xoá [ p 0 , p 3 ] và gán p 0 , p 4 , p 3 , p 4 , p 0 , p 2 , p 2 , p 3 ; gán Q : Q F 1 p 0 p 3 p 4 , p 0 p 2 p 3 ;
- với e p 0 , p 4 p 0 , p 4 , p 3 , p 4 , p 0 , p 2 , p 2 , p 3 thì F 2 p 0 p 4 p 5 xoá [ p 0 , p 4 ] và gán p 0 , p 5 , p 4 , p 5 , p 3 , p 4 , p 0 , p 2 , p 2 , p 3 ; gán Q : Q F 1 p 0 p 4 p 5 , p 0 p 3 p 4 , p 0 p 2 p 3 ;
- với e p 0 , p 5 p 0 , p 5 , p 4 , p 5 , p 3 , p 4 , p 0 , p 2 , p 2 , p 3 thì F 2 p 0 p 5 p 1 xoá [ p 0 , p 5 ] và gán p 0 , p 1 , p 5 , p 1 , p 4 , p 5 , p 3 , p 4 , p 0 , p 2 , p 2 , p 3 ; gán Q : Q F 1 p 0 p 5 p 1 , p 0 p 4 p 5 , p 0 p 3 p 4 , p 0 p 2 p 3 ;
- với e p 0 , p 1 p 0 , p 1 , p 5 , p 1 , p 4 , p 5 , p 3 , p 4 , p 0 , p 2 , p 2 , p 3 thì F 2 p 0 p 1 p 2 xoá [ p 0 , p 1 ].[ p 0 , p 2 ] và gán p 1 , p 2 , p 5 , p 1 , p 4 , p 5 , p 3 , p 4 , p 2 , p 3 ; gán Q : Q F 1 p 0 p 1 p 2 , p 0 p 5 p 1 , p 0 p 4 p 5 , p 0 p 3 p 4 , p 0 p 2 p 3 ;
- với e p 1 , p 2 p 1 , p 2 , p 5 , p 1 , p 4 , p 5 , p 3 , p 4 , p 2 , p 3 thì F 2 p 1 p 2 p 5 xoá [ p 1 , p 2 ].[ p 5 , p 1 ] và gán p 2 , p 5 , p 4 , p 5 , p 3 , p 4 , p 2 , p 3 ; gán Q : Q F 1 p 1 p 2 p 5 , p 0 p 1 p 2 , p 0 p 5 p 1 , p 0 p 4 p 5 , p 0 p 3 p 4 , p 0 p 2 p 3 ;
- với e p 2 , p 5 p 2 , p 5 , p 4 , p 5 , p 3 , p 4 , p 2 , p 3 thì F 2 p 2 p 5 p 3 xoá p 2 , p 5 , p 2 , p 3 và gán p 5 , p 3 , p 4 , p 5 , p 3 , p 4 ; gán Q : Q F 1 p 2 p 5 p 3 , p 1 p 2 p 5 , p 0 p 1 p 2 ,
- với e p 5 , p 3 p 5 , p 3 , p 4 , p 5 , p 3 , p 4 thì F 2 p 5 p 3 p 4 xoá p 5 , p 3 , p 4 , p 5 , p 3 , p 4 và gán ; gán Q : Q F 1 p 5 p 3 p 4 , p 2 p 5 p 3 , p 1 p 2 p 5 , p 0 p 1 p 2 ,
Q là tập có thứ tự các mặt cực biên của conv (xem hình 12 (b))
MỐI LIÊN HỆ GIỮA MIỀN HẠN CHẾ TRONG KHÔNG GIAN 2 - CHIỀU VÀ BAO LỒI CỦA TẬP HỮU HẠN ĐIỂM
2.1 Miền hạn chế và mặt định hướng trong không gian 2 - chiều
Giả sử rằng tập hợp điểm { p i x i , y i , z i E 3 , i 0 , 1 , , n 1}, với n 4, được nằm trong hình hộp chữ nhật có các mặt xung quanh là x x max , x x min , y y max , y y min , z z max , z z min Hình chữ nhật mn n m là một mặt của hình hộp chữ nhật, trong đó m n là giao của hai mặt x max và z min, còn mn là giao của hai mặt x max và z max Các điểm a , b , p nằm trong không gian thực và cắt mặt mn , m n tại các điểm u , u Chúng tôi ký hiệu a , b , p , u p , u p là hình chiếu tương ứng của a , b , p , u , u lên mặt phẳng Oyz theo phương song song với trục Ox Theo Mệnh đề 1.21, trong mặt phẳng Oyz, các điểm a , b , p nằm cùng phía với đường thẳng u p u p Chúng tôi ký hiệu uv là nửa mặt phẳng đóng với biên u p u p và chứa các điểm a , b , p .
Miền được gọi là miền hạn chế của mặt phẳng a , b , p (xem hình 14 và 15) Trong trường hợp
a b e , conv , chúng tôi ký hiệu thay cho e, p a , b , p .
a , b , p : 0 , y , z uv : y min y y max , z min z z max
Chú ý, nếu mặt phẳng a , b , p vuông góc với mặt phẳng Oyz (tức là,
a , b , p song song với Ox ), thì
Giả sử là tập hợp tất cả các cạnh cực biên của conv , luôn có mặt đầu tiên của conv chứa đoạn thẳng p 0 , p 1 thuộc Để xác định bao lồi conv , chúng tôi áp dụng phương pháp mặt định hướng Giả sử v là hình chiếu của v thuộc theo phương song song với trục Ox lên mặt phẳng Oyz Theo định nghĩa 2.2, nếu e a , b thuộc và tồn tại điểm p thuộc sao cho đoạn thẳng (e, p) giao với đường mn, cùng với v thuộc nằm phía dương của f e , p , thì mặt f e , p qua ba điểm a, b, p được gọi là mặt định hướng qua cạnh đầu tiên e a , b .
Mặt định hướng được xác định bằng cách chiếu tập theo phương song song với trục Ox xuống mặt phẳng Oyz Điều này có nghĩa là mặt định hướng sẽ nằm trên mặt phẳng Oyz Ngoài ra, chúng ta cũng có thể lựa chọn phương chiếu khác để mặt định hướng nằm trên các mặt phẳng khác như Oxy hoặc Oxz.
Hình 13 Nửa mặt phẳng đóng uv (phần kẻ ngang) với biên u p u p chứa a , b , p
Giả sử e = [a, b] thuộc tập hợp thực R, với n x và n y là hoành độ và tung độ của tích có hướng hai vectơ ab × ap khi p thuộc R Nếu n y khác 0, tồn tại một v thuộc R sao cho v nằm phía dương.
e p f , (nghĩa là V a , b , p , v 0 ) nếu n x 0 ii) Giả sử n x 0 Nếu f e , p là một mặt đinh hướng qua cạnh e thì
e p f , là một mặt của conv iii) Tồn tại duy nhất một điểm p sao cho hoặc f e , p là một mặt của conv với n y 0 , hoặc f e , p là một mặt định hướng qua cạnh e
Giả sử lấy được v sao cho Vấn đề lấy v như thế nào để chúng tôi sẽ trình sau thuật toán tìm bao lồi bằng miền hạn chế
Hình 14 Mặt e, p và miền hạn chế e, p tương ứng (phần kẻ sọc, bên trái đường u p u p )
Mặt f e , p là mặt định hướng qua cạnh đầu tiên e a , b m a
Mặt định hướng qua e a , b y z max z y max z min y min
Cho n n x , n y , n z là tích có hướng của hai vectơ ab ap Các điểm a, b, p cắt các mặt phẳng mn và mn tại các điểm u và u, với điều kiện n y 0 Hình chiếu của u và u theo phương song song với trục Ox lên mặt phẳng Oyz lần lượt là u p và u p Với u x max , u y , z max thuộc vào đoạn thẳng a , b , p và u p 0 , u y , z max , ta có thể rút ra các thông tin quan trọng về vị trí và hình chiếu của các điểm này.
Hình 15 Mặt e, p và miền hạn chế e, p tương ứng (phần kẻ sọc, bên phải đường u p u p )
Mặt f e , p là mặt định hướng qua cạnh đầu tiên e a , b y z max z y max z min y min
Mặt định hướng qua cạnh e a , b b a p
, , , (xem hình 16) Lấy v a , b , p sao cho vv song song với trục Ox , từ đó chúng tôi có
Đặt s : u p y u p y p z u p z p y u p y u p z u p z Giả sử n n x , n y , n z là tích có hướng của u p và u u Khi đó, n n x , n y , n z là vectơ pháp tuyến của
Hình 16 Tương ứng với hình 15, nếu nhìn mặt Oyz từ phía x thì e, p là miền hạn chế tương ứng V a b p v n vu n vv n x v x v x
, Khi đó, với mọi v sao cho
Vì u p u y y , u p u y y , u p u z z , p y p y , p z p z và (5), ta có y z y y n n z u z u ( max min )
và s p z u z u y u y u z u z p y u y n x Từ min max z z và x max p x , ta có n y 0
Do đó n ab ap và n u p u u là các vectơ pháp tuyến tương ứng của các mặt phẳng a , b , p , n x , n y , n z n x , n y , n z với R, 0 Mặt phẳng
a , b , p có phương trình là x n x y n y z n z d Khi đó, d d và z z y y x x z z y y x x n v n v n v n v n v n v d
Chứng minh mệnh đề 2.3: i) Lấy v sao cho Xét hai trường hợp sau
Trường hợp 1 Điểm p nằm bên trái của đường u p u p Khi đó 0 s n x và v y v y Từ n x 0, n y 0 và v y v y , chúng tôi lấy
max nên ta có d x max n x v z n z v y n y 0 Từ n x 0 và x z z y y x n n v n v v d
ta có v x x max Do đó v x v x Từ đó, ta có
V Vì a , b , p , v không đồng phẳng và V a , b , p , v 0 nên v nằm phía dương của mặt f e , p
Trường hợp 2 Điểm p nằm bên phải của đường u p u p Khi đó n x s
0 và v y v y Lập luận tương tự trường hợp 1 ở trên ta có
Khi v nằm phía dương của mặt f(e, p) và n y ≠ 0, giả sử mặt định hướng qua e = [a, b] là f(e, p) với p ∈ ℝ Từ đó, ta có v ∈ ℝ sao cho v nằm phía dương của mặt f(e, p), dẫn đến (a, b, p) là mặt của convℝ Hơn nữa, từ e = [a, b] là cạnh cực biên của convℝ, ta có mặt f(e, p) với p ∈ ℝ Xét trường hợp mặt f(e, p) không song song với mn (nghĩa là n y ≠ 0).
e p f , là một mặt định hướng Vì thế, tồn tại duy nhất mặt định hướng qua cạnh e □
Lấy v u p , u p sao cho v v song song với Oy Do đó v 0 , v y , v z (xem hình 17 và 18) Mặt phẳng a , b , p có phương trình xn x yn y zn z d và có vectơ pháp tuyến là n ( n x , n y , n z )
Vì a , b , p mn tại một điểm duy nhất nên
0 y n Rõ ràng, v 0 , v y , v z u p , u p Theo Định lý Thales, ta có
Hình 17 Nếu x max 0 và u p nằm phía trên a , b , p thì miền hạn chế (phần kẻ sọc) nằm phía dưới u p u p z y
a , b , p miền hạn chế y max z max y min z min
min max min min max z z u u z v u z v y z y z y y
Mặt khác ta có, u x max , u y , z max ( a , b , p ) và u x max , u y , z max ( a , b , p ) suy ra z y y x z z y y x x n u n u n x n u n z n u d max max và z y y x z z y y x x n u n u n x n u n z n u d max min
Từ đó ta có y z x y p n n z n x u d u y max max
Hình 18 Nếu x max 0 và u p nằm phía dười a , b , p thì miền hạn chế (phần kẻ sọc) nằm phía trên u p u p z y 0 a p b u p u p v v
Giả sử a, b, p thuộc tập số thực và n là vectơ pháp tuyến của mặt phẳng xác định bởi a, b, p Khi đó, điểm u p sẽ nằm phía trên mặt phẳng nếu và chỉ nếu điều kiện max < 0 được thỏa mãn, tương ứng với việc điểm này nằm phía dưới mặt phẳng khi max > 0.
Từ d x max n x u y n y z max n z , u p 0 , u y , z max nằm phía trên (tương ứng, phía dưới) mặt phẳng a , b , p khi và chỉ khi z y y n n u z d max (tương ứng, z y y n n u z d max ), nghĩa là, z z x n n z n z max x max max
(tương ứng, z z x n n z n z max x max max
) Điều này tương đương với max 0 z x n n x (tương ứng, max 0 z x n n x ) □
chiều
Miền hạn chế và mặt định hướng trong không gian 2 – chiều
Giả sử rằng tập hợp điểm { p i x i , y i , z i E 3 , i 0 , 1 , , n 1}, với n 4, nằm trong một hình hộp chữ nhật có các mặt xung quanh là x x max , x x min , y y max , y y min , z z max , z z min Mặt chữ nhật mn n m là một mặt của hình hộp chữ nhật, trong đó m n là giao của hai mặt x max và z min, còn mn là giao của hai mặt x max và z max Các điểm a, b, p thuộc cắt mn và m n tại các điểm u, u tương ứng Chúng tôi ký hiệu a , b , p , u p , u p là hình chiếu của a , b , p , u , u lên mặt phẳng Oyz theo phương song song với trục Ox Theo Mệnh đề 1.21, trong mặt Oyz, các điểm a , b , p nằm cùng phía với đường thẳng u p u p Chúng tôi ký hiệu uv là nửa mặt phẳng đóng với biên u p u p và chứa a , b , p .
Miền được gọi là miền hạn chế của mặt phẳng a , b , p (xem hình 14 và 15) Trong trường hợp
a b e , conv , chúng tôi ký hiệu thay cho e, p a , b , p .
a , b , p : 0 , y , z uv : y min y y max , z min z z max
Chú ý, nếu mặt phẳng a , b , p vuông góc với mặt phẳng Oyz (tức là,
a , b , p song song với Ox ), thì
Giả sử là tập hợp tất cả các cạnh cực biên của conv , luôn có mặt đầu tiên của conv chứa đoạn thẳng p 0 , p 1 thuộc Để xác định bao lồi conv , chúng tôi áp dụng phương pháp mặt định hướng Giả sử v là hình chiếu của v ∈ theo phương song song với trục Ox lên mặt phẳng Oyz Theo định nghĩa 2.2, nếu e = a , b thuộc và tồn tại p ∈ sao cho e và p giao với đường mn, cùng với v ∈ nằm phía dương của f e , p , thì mặt f e , p đi qua ba điểm a, b, p được gọi là mặt định hướng qua cạnh đầu tiên e = a , b .
Trong Định nghĩa 2.2, mặt định hướng được xác định bằng cách chiếu tập theo phương song song với trục Ox xuống mặt phẳng Oyz Điều này có nghĩa là mặt định hướng sẽ nằm trên mặt phẳng Oyz Ngoài ra, chúng ta cũng có thể lựa chọn phương chiếu khác để mặt định hướng nằm trên các mặt phẳng khác như Oxy hoặc Oxz.
Hình 13 Nửa mặt phẳng đóng uv (phần kẻ ngang) với biên u p u p chứa a , b , p
Giả sử e = [a, b] thuộc tập hợp các số thực, với n x và n y lần lượt là hoành độ và tung độ của tích có hướng hai vectơ ab và ap, khi p thuộc tập hợp các số thực Nếu n y khác 0, tồn tại một v thuộc tập hợp các số thực sao cho v nằm phía dương.
e p f , (nghĩa là V a , b , p , v 0 ) nếu n x 0 ii) Giả sử n x 0 Nếu f e , p là một mặt đinh hướng qua cạnh e thì
e p f , là một mặt của conv iii) Tồn tại duy nhất một điểm p sao cho hoặc f e , p là một mặt của conv với n y 0 , hoặc f e , p là một mặt định hướng qua cạnh e
Giả sử lấy được v sao cho Vấn đề lấy v như thế nào để chúng tôi sẽ trình sau thuật toán tìm bao lồi bằng miền hạn chế
Hình 14 Mặt e, p và miền hạn chế e, p tương ứng (phần kẻ sọc, bên trái đường u p u p )
Mặt f e , p là mặt định hướng qua cạnh đầu tiên e a , b m a
Mặt định hướng qua e a , b y z max z y max z min y min
Cho n n x , n y , n z là tích có hướng của hai vectơ ab ap Vectơ (a, b, p) cắt các đường mn tại các điểm u và u, với điều kiện n y 0 Hình chiếu u p của u theo phương song song với trục Ox lên mặt phẳng Oyz cho thấy u x max , u y , z max thuộc vào (a, b, p) và u p 0 , u y , z max .
Hình 15 Mặt e, p và miền hạn chế e, p tương ứng (phần kẻ sọc, bên phải đường u p u p )
Mặt f e , p là mặt định hướng qua cạnh đầu tiên e a , b y z max z y max z min y min
Mặt định hướng qua cạnh e a , b b a p
, , , (xem hình 16) Lấy v a , b , p sao cho vv song song với trục Ox , từ đó chúng tôi có
Đặt s : u p y u p y p z u p z p y u p y u p z u p z Giả sử n n x , n y , n z là tích có hướng của u p và u u Khi đó, n n x , n y , n z là vectơ pháp tuyến của
Hình 16 Tương ứng với hình 15, nếu nhìn mặt Oyz từ phía x thì e, p là miền hạn chế tương ứng V a b p v n vu n vv n x v x v x
, Khi đó, với mọi v sao cho
Vì u p u y y , u p u y y , u p u z z , p y p y , p z p z và (5), ta có y z y y n n z u z u ( max min )
và s p z u z u y u y u z u z p y u y n x Từ min max z z và x max p x , ta có n y 0
Do đó n ab ap và n u p u u là các vectơ pháp tuyến tương ứng của các mặt phẳng a , b , p , n x , n y , n z n x , n y , n z với R, 0 Mặt phẳng
a , b , p có phương trình là x n x y n y z n z d Khi đó, d d và z z y y x x z z y y x x n v n v n v n v n v n v d
Chứng minh mệnh đề 2.3: i) Lấy v sao cho Xét hai trường hợp sau
Trường hợp 1 Điểm p nằm bên trái của đường u p u p Khi đó 0 s n x và v y v y Từ n x 0, n y 0 và v y v y , chúng tôi lấy
max nên ta có d x max n x v z n z v y n y 0 Từ n x 0 và x z z y y x n n v n v v d
ta có v x x max Do đó v x v x Từ đó, ta có
V Vì a , b , p , v không đồng phẳng và V a , b , p , v 0 nên v nằm phía dương của mặt f e , p
Trường hợp 2 Điểm p nằm bên phải của đường u p u p Khi đó n x s
0 và v y v y Lập luận tương tự trường hợp 1 ở trên ta có
Khi v nằm phía dương của mặt f(e, p) với p thuộc tập số thực, và n_y khác 0, ta giả sử mặt định hướng qua e = [a, b] là f(e, p) Từ đó, v thuộc tập số thực, cho thấy v cũng nằm phía dương của mặt f(e, p), và (a, b, p) trở thành mặt của convℝ Đặc biệt, từ e = [a, b] là cạnh cực biên của convℝ, ta có mặt f(e, p) với p thuộc tập số thực Xét trường hợp mặt f(e, p) không song song với mn, tức là n_y khác 0.
e p f , là một mặt định hướng Vì thế, tồn tại duy nhất mặt định hướng qua cạnh e □
Lấy v u p , u p sao cho v v song song với Oy Do đó v 0 , v y , v z (xem hình 17 và 18) Mặt phẳng a , b , p có phương trình xn x yn y zn z d và có vectơ pháp tuyến là n ( n x , n y , n z )
Vì a , b , p mn tại một điểm duy nhất nên
0 y n Rõ ràng, v 0 , v y , v z u p , u p Theo Định lý Thales, ta có
Hình 17 Nếu x max 0 và u p nằm phía trên a , b , p thì miền hạn chế (phần kẻ sọc) nằm phía dưới u p u p z y
a , b , p miền hạn chế y max z max y min z min
min max min min max z z u u z v u z v y z y z y y
Mặt khác ta có, u x max , u y , z max ( a , b , p ) và u x max , u y , z max ( a , b , p ) suy ra z y y x z z y y x x n u n u n x n u n z n u d max max và z y y x z z y y x x n u n u n x n u n z n u d max min
Từ đó ta có y z x y p n n z n x u d u y max max
Hình 18 Nếu x max 0 và u p nằm phía dười a , b , p thì miền hạn chế (phần kẻ sọc) nằm phía trên u p u p z y 0 a p b u p u p v v
Giả sử a, b, p thuộc tập hợp số thực và n là vectơ pháp tuyến của mặt phẳng xác định bởi a, b, p Điểm u p sẽ nằm phía trên mặt phẳng này khi điều kiện max < 0 được thỏa mãn, ngược lại, điểm sẽ nằm phía dưới mặt phẳng khi max > 0.
Từ d x max n x u y n y z max n z , u p 0 , u y , z max nằm phía trên (tương ứng, phía dưới) mặt phẳng a , b , p khi và chỉ khi z y y n n u z d max (tương ứng, z y y n n u z d max ), nghĩa là, z z x n n z n z max x max max
(tương ứng, z z x n n z n z max x max max
) Điều này tương đương với max 0 z x n n x (tương ứng, max 0 z x n n x ) □
Giả sử [a, b] là cạnh của conv R, với p thuộc R và u p nằm phía trên (hoặc phía dưới) mặt phẳng (a, b, p) Nếu x_max > 0, miền sẽ nằm phía dưới (hoặc phía trên) đường định hướng u p trên mặt phẳng Oyz khi nhìn từ phía x ≈ +∞ Ngược lại, nếu x_max < 0, miền sẽ nằm phía trên (hoặc phía dưới) đường định hướng p trên mặt phẳng Oyz Thêm vào đó, nếu n ρ = (n x, n y, n z) là tích có hướng của hai vectơ ab × ap, điều này cũng có ảnh hưởng đến vị trí của miền trong không gian.
a , b , p thì v nằm phía dương của f a , b , p iii) Nếu (7) không đúng với n ab ap và thì f a , b , p không là mặt định hướng qua cạnh a, b
Chứng minh: i) Đầu tiên, chúng tôi xét trường hợp u p nằm phía trên mặt phẳng a , b , p
Từ n z 0, u y u y 0, có hai khả năng sau:
Khi \( u_y - u_y < 0 \) (xem hình 14 và 17), điều này dẫn đến \( n_z < 0 \), và chúng tôi cần chứng minh rằng nó nằm phía dưới (hoặc phía trên) đường định hướng \( u_p u_p \) Dựa vào Mệnh đề 1.21, chúng tôi chứng minh rằng \( p' \) nằm bên trái đường định hướng \( u_p u_p \) khi quan sát mặt phẳng Oyz từ phía \( x \approx +\infty \) và nhìn trục Oy từ phải qua trái Theo Mệnh đề 2.4, ta có \( \max n_x - n_z < 0 \), do đó \( s_x \max < 0 \) Nếu \( x_{\max} > 0 \) (hoặc \( x_{\max} < 0 \)), thì \( p' \) cũng nằm bên trái (hoặc bên phải) đường định hướng \( u_p u_p \) Kết luận, điều này cho thấy nó nằm phía dưới (hoặc phía trên) đường định hướng \( u_p u_p \) trên mặt phẳng Oyz khi nhìn từ phía \( x \approx +\infty \).
Khả năng 2 cho thấy khi \( u_y - u_y > 0 \), thì \( n_z > 0 \) và \( sx_{max} > 0 \) Điều này có nghĩa là nếu \( sx_{max} > 0 \) (tương ứng, \( sx_{max} < 0 \)), thì điểm sẽ nằm bên trái (tương ứng, bên phải) đường định hướng \( u_p \) trên mặt phẳng Oyz Do đó, điểm sẽ nằm phía dưới (tương ứng, phía trên) đường định hướng \( u_p \) khi nhìn từ phía.
Sau đó, chúng tôi xét trường hợp u p nằm phía dưới mặt phẳng a , b , p Khi đó, có hai khả năng sau:
Khi khả năng 3 xảy ra với điều kiện \( u_y - u_y < 0 \), dẫn đến \( n_z < 0 \) Theo Mệnh đề 2.4, ta có \( \max(s_x) > 0 \) Nhìn từ mặt phẳng Oyz khi \( x \approx +\infty \) và trục Oy từ phải qua trái, nếu \( x_{\max} > 0 \) (tương ứng với \( x_{\max} < 0 \)), thì \( p' \) nằm bên phải (hoặc bên trái) đường định hướng \( u_p \) Do đó, \( p' \) cũng nằm bên phải (hoặc bên trái) đường định hướng \( p \) trên mặt phẳng Oyz khi nhìn từ phía \( x \approx +\infty \).
Khi khả năng 4 xảy ra với điều kiện u y - u y > 0, ta có n z > 0 và sx max < 0 Điều này cho thấy nếu max > 0 (hoặc x max < 0), thì điểm nằm bên trái (hoặc bên phải) đường định hướng u p Hơn nữa, điểm này sẽ nằm phía trên (hoặc phía dưới) đường định hướng u p trên mặt phẳng Oyz khi nhìn từ phía x ≈ +∞.
v x v x x max n x 0 (tương ứng, v x v x x max n x 0 ) (8) Giả sử u p nằm phía trên mặt phẳng a , b , p và giả sử ta có (8) (nghĩa là,
v x v x x max n z 0 ) Từ Mệnh đề 2.4, ta có max 0 z x n n x Từ (8), ta có
Giả sử u p nằm phía dưới mặt phẳng a , b , p và giả sử ta có (8) (nghĩa là,
v x v x x max n z 0 ) Từ Mệnh đề 2.4, ta có max 0 z x n n x Từ (8), ta có
Mặt phẳng (a, b, p) có vectơ pháp tuyến n = ab × ap Nếu giả sử rằng điều kiện (7) không đúng với vectơ pháp tuyến này, chúng ta có thể thực hiện chứng minh tương tự như đã nêu ở phần (ii).
V , và do đó v không nằm phía dương của f a , b , p với
Do đó, mặt f a , b , p không là mặt định hướng qua cạnh e a , b □
2.2 Thuật toán tìm bao lồi của tập hữu han điểm trong không gian 3 - chiều bằng miền hạn chế trong không gian 2 - chiều
Thuật toán này được cải biên từ thuật toán gói quà tìm bao lồi cho tập hữu hạn điểm trong không gian 3 chiều Quá trình tìm mặt đầu tiên F1 bắt đầu từ cạnh cực biên đầu tiên e, dựa trên phương pháp mặt định hướng Bao lồi được hình thành từ các mặt, trong đó một mặt được xác định từ miền hạn chế trong không gian 2 chiều Ý tưởng chính của thuật toán là xuất phát từ cạnh cực biên đầu tiên e = [a, b] để tìm điểm.
Để xác định mặt đầu tiên của convℝ, chúng ta cần điều kiện V(a, b, p, v) > 0 với mọi v thuộc ℝ không phải là a, b, p Do đó, F₁ = (a, b, p) trở thành mặt đầu tiên của convℝ Để đơn giản hóa quá trình tính toán, chúng tôi sử dụng miền hạn chế của mặt (a, b, p), nhằm chỉ cần xem xét một số giá trị nhất định mà không cần kiểm tra với mọi v thuộc ℝ không phải là a, b, p.
V , , , , với mọi v \ a , b , p mà còn nếu thì không phải tính V a , b , p , v
Kết quả tính toán
Thuật toán gói quà và thuật toán mới được trình bày trong mục 2.2 được thực hiện bằng ngôn ngữ lập trình C Việc triển khai thuật toán gói quà có thể tham khảo trong tài liệu [7] Mã nguồn và chương trình được chạy trên hệ điều hành GNU C trong SuSe Linux 10.0, sử dụng bộ xử lý Pentium IV.
Tập { p i x i , y i , z i : x , y , z R, z i x i 2 y i 2 , i 0 , 1 , , n 1 } là tập hợp các điểm ngẫu nhiên trên mặt của paraboloid, với tất cả các điểm trong đều là điểm cực biên của bao lồi conv Thuật toán tìm bao lồi bằng miền hạn chế, được mô tả trong mục 2.2 và thực hiện bởi (10), cho thấy hiệu suất vượt trội so với thuật toán gói quà.
Input (số điểm ngẫu nhiên của trong 3D) Thuật toán gói quà Thuật toán miền hạn chế n Thời gian thực hiện thuật toán tính theo giây
Bảng 1: Thời gian chạy của thuật toán mới được trình bày trong mục 2.2 và thuật toán gói quà trình bày trong [11] (tính theo giây) với
n i là tập điểm ngẫu nhiên nằm trong hình vuông kích thước 200x200
Trong bài viết này, chúng tôi khám phá mối quan hệ giữa miền hạn chế trong không gian 2 chiều và bao lồi của tập hữu hạn điểm trong không gian 3 chiều Chúng tôi đã đạt được một số kết quả đáng chú ý và đề xuất những hướng nghiên cứu phát triển cho luận văn.
Thuật toán gói quà tìm bao lồi cho tập hữu hạn điểm trong không gian 3 chiều được trình bày chi tiết trong mục 1.4, kèm theo ví dụ minh họa cụ thể để làm rõ cách thức hoạt động của thuật toán này.
Chứng minh lại một số tính chất của miền hạn chế và mặt định hướng trong không gian E 3 (mục 2.1)
Trình bày lại một cách chi tiết thuật toán tìm bao lồi trong không gian
3 – chiều bằng miền hạn chế trong không gian 2 - chiều và đưa ra ví dụ minh hoạ cho thuật toán này (mục 2.2)
Trình bày lại một số kết quả tính toán của hai thuật toán đã được thực thi trên máy tính (mục 2.3)
2 Hướng phát triển luận văn
Nghiên cứu mặt định hướng trong các mặt phẳng Oxy, Oxz
Sử dụng miền hạn chế để tìm bao lồi của tập hữu hạn điểm trong không gian nhiều chiều
Sử dụng mặt định hướng trong việc xây dựng tam giác phân Delaunay
Bộ điểm và các mặt của bao lồi convP trong ví dụ của mục 2.2
% The total number of non-visiting points: 15385
%% List of all hull faces:
[1] P T An (2010-2012), Bài giảng môn hình học tính toán, Viện Toán học, Hà Nội
[2] N H Điển (2005), Một số chuyên đề hình học tổ hợp, NXB Giáo dục
[3] Đ V Lưu và P H Khải (2000), Giải tích lồi, NXB Khoa học và kỹ thuật
[4] P T An (2007), A modification of Graham’s algorithm for determining the convex hull of a finite planar set, Annales Mathematicae et
[5] P T An (2010), Method of Orienting Curves for determining the convex hull of a finite set of poínts in the plane, Optimization, 59 (2) pp 175-179
[6] P T An và L H Trang (2011), An efficient convex hull algorithm for finite points sets in 3D based on the method of orienting curves,
[7] T Lambert, Gift wrapping algorithm in three dimensions, http://www.cse.unsw.edu.au/ ~ lambert/java/3d/giftwrap.html
[8] S R Ley (1982), Convex sets and their applications, John Wiley & Sons
[9] P McMullen và G C Shephard (1971), Convex Polytopes and the
Upper Bound Cojnecture, Cambridge University Press.