Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TOÁN 1.1 Các bài toán của hình học tính toán Hình họctính toánlà mộtchuyên ngành củakhoa họcmáy tínhnghiên cứucácthuật toáncó nội dung hình học. Một sốbài toánhình họcphát sinh hoàn toàntừviệc nghiên cứu cácthuật toánhình học tính toánvà cácbài toánnàycũng đượcxemlà một phần củahình học tính toán. Hình học tính toán nghiên cứusự phức tạpcủa cácbài toánhình học, xây dựngcấu trúc dữ liệuđểlưu trữcác loại dữ liệuhình học, thiết kếthuật toáncho cácbài toánhình học và khám phácác tính chấthình học. Những vấn đề cốt lõi trong hình học tính toán có thể được chia với nhiều cách khác nhau, theo nhiều tiêu chí khác nhau.
Ở đây, có thể phân loại các bài toántrong hình học tính toán thành các lớp bài toán như dưới đây[1].1 Bài toán tĩnh Trong cácbài toántĩnhcho trướcđầu vàovàđầu ratương ứngcần phải đượcxây dựng hoặcđược tìm thấy.Một sốbài toáncơ bảncủa loại nàylà: Convex Hull: Cho tập hợp các điểm và yêu cầu tìm đa giác lồi nhỏ nhất chứa tất cả các điểm đó. Line segment intersection: Cho tập hợp các đoạn thẳng và yêu cầu tìm điểm cắt nhau giữa các đoạn thẳng trongtập hợp cho trước. Polygon cutting: Chia đa giác thành các dạng hình học khác với tổng chiều dài được chia là nhỏ nhất. Voronoi diagram: Cho tập hợp các điểm và yêu cầu tìm phân vùng không gian theo các điểm đóng.
Closest pair of points: Cho tập hợp các điểm và yêu cầutìm cặp điểm có khoảng cách nhỏ nhất. Euclidean shortest path: Nối hai điểm trong không gian Euclide bởi một đường đi ngắn nhất. Polygon triangulation: Cho trước một đa giác và yêu cầuphân chia phần trong của đa giác thành các tam giác. Độ phức tạptính toáncholớp cácbài toánnày làước tính về thời gian TIEU LUAN MOI download : skknchat@gmail.com 7 vàkhông gian cần thiết để giải quyếtmột trường hợp bài toánnhất định.2Bài toán động Thêm một lớpchínhlà các bài toánđộng,vớimục tiêu là đểtìmthuật toánhiệu quảcho việc tìm lời giảinhiều lầnsau mỗi lầnsửa đổigia tăng dữ liệu đầu vào.
Các thuật toáncho bài toánthuộc loại nàythườngliên quan đếncấu trúcdữ liệu động. Bất kỳcác bài toánhình họctính toáncó thể đượcchuyển đổi thành mộtbài toán động.Bài toántìm kiếmphạm vicó thểđược chuyển đổi thànhbài toántìm kiếmphạm vi động,bằng cách cung cấpbổ sunghoặcxóacác điểm.Cácbài toánbao lồi độnglà đểlưu vết cácbaolồi,chẳng hạn như đối với tập hợp các điểmthay đổi động, khicác điểmđầu vàođược chènhoặcxóa.3Bài toán truy vấn hình học Bài toán truy vấn hình họcthường gọi làbài toántìm kiếmhình học,đầu vàobao gồm hai phần: không gian tìm kiếmvà truy vấn với thay đổitrongcác trường hợpbài toán.Không giantìm kiếmthườngphải đượcxử lí trước, trong cùng một cách mànhiều truy vấn có thể đượctrả lờimột cách hiệu quả.Một sốbài toántruy vấnhình họccơ bảnlà: Range Searching: Xử lí trướctập hợp các điểm và yêu cầuđếm số lượng cácđiểmnằm trong vùngtruy vấn một cách hiệu quả. Points Location: Cho phân vùngcủa không gianthành các ô và yêu cầu tạo racấu trúcdữ liệuhiệu quảchoô nơi điểmtruy vấnđược định vị. Nearest neighbor:Cho tập hợp các điểm và yêu cầutìmđiểm nằm gần nhất vớiđiểmtruy vấn một cách hiệu quả.
Raytracing: Cho tập hợp các đối tượngtrong không gian và yêu cầu tạo racấu trúcdữ liệuhiệu quảchođối tượngcó tiatruy vấncắtđầu tiên. Nếu không gian tìm kiếm là cố định, độ phức tạp tính toán cho bài toán truy vấn hình họcđược ước tính bởi thời gian và không gian cần thiết để xây dựng các cấu trúc dữ liệu tìm kiếm và thời gian trả lời các truy vấn.4Các biến thể Một số bài toáncó thểđược xem làthuộcmột trong cácloại trên,tùy thuộcvào bối cảnh.Chẳng hạn xét bài toán: Point in polygon – Xác định một điểm nằm trong hay nằm ngoài đa giác cho trước.Trong một vài tình huống của bài toán truy vấn có thể kỳ vọng hợp lí vào thứ tự các truy vấn, hoặc có thể được TIEU LUAN MOI download : skknchat@gmail.com 8 khai thác với cấu trúc dữ liệu hiệu quả hoặc ước tính độ phức tạp chặt chẽ hơn.2 Các đối tượng hình học Máy tính ngày càng được sử dụng nhiều hơn để giải quyết các bài toán có quy mô lớn về hình học. Các đối tượng hình học cơ bản như điểm, đoạn thẳng và đa giác là nguồn gốc của tập đáng kể các bài toán và thuật toán.1 Điểm Trong không gian hai chiều, đối tượng cơ sở là điểm được biểu diễn bởi một cặp số nguyên – tọa độ của điểm đó trong hệ trục tọa độ Descart. Một điểm trong mặt phẳng có tọa độ và tọa độ , kí hiệu [13].2 Đoạn thẳng Một tổ hợp lồi của hai điểm phân biệt và là một điểm bất kỳ sao cho và với.
Hay viết dưới dạng khác. Đoạn thẳng là tập hợp mọi tổ hợp lồi của và , kí hiệu , với và các điểm đầu mút của đoạn thẳng. Đoạn thẳng có hướng là đoạn thẳng được định hướng từ đến , kí hiệu [13].3 Vectơ Vectơ là một đoạn thẳng có hướng. Vectơ có điểm đầu và điểm cuối , được kí hiệu.
Khi không cần chỉ rõ điểm đầu, điểm cuối ta kí hiệu [13]. Tọa độ của vectơ là = với ; .3 Một số bài toán hình học và thuật toán 1.1 Bài toán xác định cặp đoạn thẳng bất kỳ cắt nhau Thuật toánxác định cặp đoạn thẳng bất kỳtrong tập hợp các đoạn thẳng cắt nhau sử dụng “kỹ thuật quét”. Trongkỹ thuật quét, đường thẳngquétdọcđiquatập hợp các đối tượng hình họctừtráisangphải vàxem xét tất cảcácđiểm đầu mút củađoạn thẳng theo thứ tự từtráisangphải vàkiểm trasự cắt nhau mỗi khichạmmộtđiểm đầu mút.1 Phát biểu bài toán Cho tập hợp các đoạn thẳng trong mặt phẳng và yêu cầu xác định có tồn tại cặp đoạn thẳng nào cắt nhau hay không. Giả sử rằng không có các đoạn thẳng TIEU LUAN MOI download : skknchat@gmail.com 9 dọc và không có ba đoạn thẳng nào giao nhau tại một điểm.2 Thuật toán Một thứ tự hoàn toàn (total order) trên các đoạn thẳng cắt nhau bởi đường thẳng quét dọc được định nghĩa như sau[13].
- Hai đoạn thẳng và là có thể so sánh được tại nếu đường thẳng quét dọc tại ví trí cắt cả hai đoạn thẳng đó. - Nếu và là có thể so sánh tại và giao điểm của với đường thẳng quét tại ở cao hơn với giao điểm của với cùng đường thẳng quét đó thì ta nói rằng ở trên tại , kí hiệu .1 -Thứ tự giữa cácđoạnthẳng vớiđườngthẳngquétdọc Với bất kỳ cho trước, mối quan hệ là một thứ tự hoàn toàn của đoạn thẳng cắt đường thẳng quét tại. Những mối quan hệ , , , và ; Đoạn thẳng không so sánh được với các đoạn thẳng khác, hình 1. Khi đoạn thẳng và giao nhau, nhưng ; mọi đường thẳng quét đi qua vùng bóng mờ đều có và nằm liên tiếp nhau trong quan hệ thứ tự , hình 1.
Khi di chuyển đường thẳng quét, thuật toán thường phải quản lí hai tập hợp dữ liệu sau: - Tình trạng đường thẳng quét cho biết thứ tự giữa các đoạn thẳng được cắt bởi đường thẳng quét. - Lịch các điểm biến cố là một dãy các tọa độ của các điểm đầu mút được sắp thứ tự từ trái sang phải để xác định vị trí dừng của đường thẳng quét. Gọi mỗi vị trí dừng như một điểm biến cố. Tình trạng của đường thẳng quét thay đổi tại các vị trí dừng của đường thẳng quét.
TIEU LUAN MOI download : skknchat@gmail.com 10 Các thao tác của trình trạng đường thẳng quét để duy trì truy vấn. - INSERT( ): chèn đoạn thẳng vào. - DELETE( ): xóa đoạn thẳng khỏi. - ABOVE( ): trả về đoạn thẳng ở ngay trên trong.
- BELOW( ): trả về đoạn thẳng ở ngay dưới s trong. Cấu trúc dữ liệu cho lịch điểm biến cố (event-point schedule) - Mỗi điểm đầu mút của các đoạn thẳng trong là một điểm biến cố, là vị trí đường thẳng quét nơi thứ tự thay đổi. - Lịch điểm biến cố là tĩnh và được xây dựng bằng cách sắp xếp các điểm đầu mút của các đoạn thẳng theo thứ tự từ trái sang phải. Nếu khi sắp xếp các điểm đầu mút của các đoạn thẳng trong từ trái sang phải nếu có nhiều điểm có cùng tọa độ thì phân giải trùng hợp như sau: - Các điểm đầu mút trái được sắp xếp trước các điểm đầu mút phải.
- Tiếp theo, các điểm đầu mút có tọa độ y nhỏ hơn được xếp trước. Sắp xếp các điểm đầu mút (x, y) theo thứ tự (x, e, y) trong đó xvàylàtọa độvới e = 0 cho điểm đầu mút trái và e = 1 cho điểm đầu mút phải. Thuật toán xác định cặp đoạn thẳng bất kỳ cắt nhaunhư sau[13]. Algorithm ANY-SEGMENTS-INTERSECT Input.
Tập hợp gồm đoạn thẳng. Cặp các đoạn thẳng trong cắt nhau thì giá trị True, ngược lại là False. Sắp xếp các điểm đầu mút của các đoạn thẳng trong từ trái sang phải, phân giải trùng hợp bằng cách đặt các điểm đầu mút trái trước các điểm đầu mút phải và kế đến phân giải trùng hợp bằng cách đặt các điểm đầu mút có tọa độ nhỏ hơn được sắp xếp trước. for mỗi điểm trong danh sách được sắp xếp của các điểm đầu mút do 4.
if là điểm đầu mút trái của đoạn thẳng then 5. return TRUE TIEU LUAN MOI download : skknchat@gmail. if là điểm đầu mút phải của đoạn thẳng then 9.3 Phân tích độ phức tạp Định lí 1.1 Gọi là tậphợp gồm đoạn thẳng, thuật toán ANY-SEGMENTS- INTERSECT thực hiện trong thời gian [13]. Thật vậy, dòng1thực hiện mấtthời gian là.
Dòng2thực hiện mất thời gian là , bằng cách sử dụngsắp xếp trộn (merge sort) hoặcheapsort. Khicó điểm biến cố, vòng lặp forcủadòng3-11thực hiện nhiều nhất là. Mỗilần lặpmất thời gian , vìmỗihoạt động cây đỏđen mấtthời gian vàbằng cách sử dụngcácphương phápkiểm tra mỗigiao điểmcần thời gian. Vì vậy, thời gianthực hiện thuật toán là .2 Bài toán tìm bao lồi Một tập hợp trong mặt phẳng được gọi là lồi nếu cho trước bất kỳ tổ hợp lồi của và nằm trong , hoặc tương đương với đoạn thẳng được chứa hoàn toàn trong [26].
q p p lồi không lồi Bao lồi của tập hợp bất kỳ là giao của tất cả các tập lồi chứa , hay bằng trực quan hơn, tập lồi nhỏ nhất chứa , kí hiệu [26].1 Phát biểu bài toán Cho là tập hợp các điểm trong mặt phẳng và yêu cầu tìm bao lồi của nó, tức là tìm đa giác lồi nhỏ nhất mà mỗi điểm của hoặc nằm trên biên của hoặc nằm trong phần trong của. TIEU LUAN MOI download : skknchat@gmail.2 -Tập hợp gồm các điểm và bao lồi 1.2 Thuật toán Thuật toán quét Graham và thuật toán bước Jarvis tìm bao lồi của tập hợp gồm điểm trong mặt phẳng. Cả hai thuật toán quét Graham và bước Jarvis đều sử dụng kỹ thuật “quét quay tròn”, các đỉnh được xử lí theo thứ tự của các góc giữa tạo với một đỉnh tham chiếu. Thuật toán quét GRAHAM [13, 17] Thuật toán quét Grahamgiải quyết bài toántìm bao lồibằng cách khởi tạongăn xếp gồm cácđiểm ứng viên.
Mỗiđiểmcủatập hợp đầu vàotrong được đẩylênđầu ngăn xếpvàcác điểmkhông phải làđỉnhcủa được loại bỏ khỏi ngăn xếpsau cùng.