Tài liệu Một số kiểu dữ liệu trừu tượng ứng dụng trong hình học tính toán

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HOA MỘT SỐ KIỂU DỮ LIỆU TRỪU TƯỢNG ỨNG DỤNG TRONG HÌNH HỌC TÍNH TOÁN LUẬN VĂN THẠC SĨ Hà Nội – 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ HOA MỘT SỐ KIỂU DỮ LIỆU TRỪU TƯỢNG ỨNG DỤNG TRONG HÌNH HỌC TÍNH TOÁN Ngành : Công nghệ Thông tin Chuyên ngành : Hệ thống Thông tin Mã số : 60 48 05 LUẬN VĂN THẠC SĨ NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. LÊ MINH HOÀNG Hà Nội – 2011 1 MỤC LỤC DANH SÁCH THUẬT NGỮ VÀ GIẢI THÍCH............................................. 2 DANH SÁCH HÌNH VẼ .................................................................................. 3 MỞ ĐẦU ........................................................................................................... 5 Chương 1 - TỔNG QUAN VỀ HÌNH HỌC TÍNH TOÁN............................. 6 1.1 Các bài toán của hình học tính toán .................................................... 6 1.2 Các đối tượng hình học ........................................................................ 8 1.3 Một số bài toán hình học và thuật toán ............................................... 8 1.3.1 Bài toán xác định cặp đoạn thẳng bất kỳ cắt nhau ........................ 8 1.3.2 Bài toán tìm bao lồi .................................................................... 11 1.3.3 Bài toán tìm cặp điểm gần nhất .................................................. 14 1.4 Kết luận ............................................................................................... 17 Chương 2 - KIỂU DỮ LIỆU TRỪU TƯỢNG TRONG HÌNH HỌC TÍNH TOÁN .. 18 2.1 Tìm kiếm phạm vi trực giao............................................................... 18 2.1.1 Mô hình quản lí đối tượng một chiều ......................................... 19 2.1.2 Mô hình quản lí đối tượng hai chiều........................................... 22 2.1.3 Mô hình quản lí đối tượng nhiều chiều....................................... 30 2.2 Cấu trúc dữ liệu hình học................................................................... 35 2.2.1 Interval trees .............................................................................. 36 2.2.2 Priority search trees.................................................................... 41 2.2.3 Segment trees ............................................................................. 45 2.3 Biến thể của các cấu trúc dữ liệu hình học ........................................ 51 2.3.1 Partition trees ............................................................................. 52 2.3.2 Multi-level partition trees ........................................................... 57 2.3.3 Cutting trees ............................................................................... 60 2.4 Kết luận ............................................................................................... 66 Chương 3 - CÀI ĐẶT VÀ ĐÁNH GIÁ.......................................................... 68 3.1 Cài đặt Kd-trees ................................................................................. 68 3.2 Cài đặt Range trees ............................................................................ 70 3.3 Cài đặt Interval trees .......................................................................... 72 3.4 Cài đặt Segment trees ......................................................................... 74 3.5 Kết luận ............................................................................................... 76 KẾT LUẬN ..................................................................................................... 77 TÀI LIỆU THAM KHẢO.............................................................................. 78 2 DANH SÁCH THUẬT NGỮ VÀ GIẢI THÍCH Số 1 Thuật ngữ Canonical subset Giải thích Tập con chính qui chiều 2 -Dimensional Kd-trees Kd-trees 3 -Dimensional Range trees Range trees chiều 4 Interval trees Cây quản lí khoảng 5 Multi-level partition trees Cây phân vùng nhiều mức 6 Partition trees Cây phân vùng 7 Priority search trees Cây tìm kiếm ưu tiên 8 Range queries Truy vấn phạm vi 9 Range trees Cây phạm vi 10 Segment trees Cây quản lí đoạn thẳng 11 Stabbing queries Truy vấn stabbing 12 Windowing queries Truy vấn cửa sổ 3 DANH SÁCH HÌNH VẼ Số Tên hình Trang Hình 1.1 Thứ tự giữacácđoạnthẳng với đườngthẳngquétdọc Hình 1.2 Tập hợp gồm các điểm và bao lồi 12 Hình 1.3 Thuật toán chỉ cần kiểm tra7 điểm trong mảng 16 Hình 2.1 Giải thíchtruy vấncơ sở dữ liệu một cách hình 18 Hình 2.2 Truy vấn phạm vi một chiều trong cây nhị phân tìm kiếm 20 Hình 2.3 Kd-trees: mặt phẳng được chia và cây nhị phân 23 Hình 2.4 Các nútcủa kd-trees vàvùngmặt phẳng 24 Hình 2.5 Truy vấn trên kd-trees hai chiều 25 Hình 2.6 Range trees hai chiều 27 Hình 2.7 Tăng tốc độ tìm kiếm bằng cách thêm các con trỏ 33 Hình 2.8 Cây chínhcủarange trees phântầng 34 Hình 2.9 Các mảngliên kếtvớicác núttrongcây chính 34 Hình 2.10 Truy vấn cửa sổ trong bản đồ của U.S. 36 Hình 2.11 Phân loại các đoạn thẳng liên quan với 38 Hình 2.12 Interval trees 39 Hình 2.13 Các đoạn thẳngcắt bởi qcóđiểm đầu mút trái 40 Hình 2.14 Heap của tập hợp {1,3,4,8,11,15,21,22,36} 42 Hình 2.15 Một tập hợp các điểm và cây tìm kiếm ưu tiên tương ứng 43 Hình 2.16 Truy vấn của cây tìm kiếm ưu tiên 43 Hình 2.17 Đoạn thẳng lưu tại v thay vì lưu trữ tại Hình 2.18 Segment trees: mũi têntừcácnúttrỏtới tập con chính qui Tập con chính qui chứacác đoạnthẳng màbao trùmsàncủamột nút, nhưng không phải làsàncủacha nó 48 Hình 2.20 Mật độ dân số của Hà Lan 51 Hình 2.21 Trả lời truy vấn nửa đường thẳng với cây nhị phân 53 Hình 2.22 Một phân vùng đơn hình tốt 54 Hình 2.23 Phân vùng mặt phẳng đơn hình và cây tương ứng 54 Hình 2.19 9 và 47 49 4 Số Tên hình Trang Hình 2.24 Trả lời truy vấn phạm vi nửa mặt phẳng với partition trees 56 Hình 2.25 Đếm phạm vi nửa mặt phẳngtrongmặt phẳng đối ngẫu 60 Hình 2.26 (1/2) - cutting kích thước 10 cho tập hợp 6 đường thẳng 61 Hình 2.27 Cáctập con chính quivàtập conđiquatam giác 62 Hình 2.28 Tìm kiếm phạm vi tam giác 63 Hình 3.1 Sơ đồ các lớp trong thực hiện Kd-trees 68 Hình 3.2 Sơ đồ các lớp trong thực hiện Range trees 70 Hình 3.3 Sơ đồ các lớp trong thực hiện Interval trees 72 Hình 3.4 Sơ đồ các lớp trong thực hiện Segment trees 74 5 MỞ ĐẦU Hình học tính toán xuất hiện từ lĩnh vực phân tích và thiết kế thuật toán trong cuối những năm 1970 và lớn mạnh trở thành một môn học với tạp chí riêng, hội nghị riêng và có một cộng đồng lớn các nhà nghiên cứu hoạt động. Hình học tính toán là một chuyên ngành khoa học máy tính nghiên cứu các thuật toán giải quyết các bài toán hình học. Hình học tính toán có ứng dụng trong nhiều lĩnh vực khác nhau như đồ họa máy tính, hệ thống thông tin địa lí, người máy, thống kê và những lĩnh vực khác mà trong đó các thuật toán hình học đóng vai trò cơ bản. Vấn đề hình học tính toán với đầu vào là mô tả kiểu của tập hợp các đối tượng hình học, ví dụ như tập hợp các điểm, tập hợp các đoạn thẳng, hoặc tập hợp các đỉnh của một đa giác theo thứ tự ngược chiều kim đồng. Đầu ra là đáp ứng với truy vấn về các đối tượng như các đường thẳng cắt nhau, hoặc có thể là một đối tượng hình học mới, ví dụ như bao lồi của tập hợp các điểm. Các đối tượng hình học như điểm, đường thẳng và đa giác là cơ sở của một loạt các ứng dụng quan trọng và làm tăng tính thú vị của tập hợp các vấn đề về thuật toán. Ngày nay, máy tính được sử dụng ngày càng nhiều hơn để giải quyết các bài toán hình học với quy mô lớn hơn. Lời giải tốt cho các bài toán thuật toán có tính chất hình học chủ yếu dựa trên hai thành phần. Một là sự hiểu biết thấu đáo các tính chất hình học của bài toán, hai là ứng dụng các kỹ thuật thuật toán và cấu trúc dữ liệu thích hợp. Trong luận văn sẽ trình bày một số kiểu dữ liệu trừu tượng và cấu trúc dữ liệu trong hình học tính toán. Những ứng dụng của các cấu trúc dữ liệu này không chỉ giới hạn trong các đối tượng hình học mà còn cho phép thiết kế những thuật toán hiệu quả, có thể xử lí các loại dữ liệu khác nhau của nhiều bài toán khác nhau. Luận văn được tổ chức thành 3 chương như sau: Chương 1 – Trình bày tổng quan về hình học tính toán như các đối tượng của hình học, một số bài toán hình học và thuật toán. Chương 2 – Mô tả kiểu dữ liệu trừu tượng trong hình học tính toán như mô hình quản lí đối tượng một chiều, hai chiều và nhiều chiều. Chương 3 – Cài đặt các cấu trúc dữ liệu, kết quả cài đặt thử nghiệm, đánh giá hiệu suất của thuật toán và chương trình. 6 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.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. Delaunay triangulation. 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. Linear programming. 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 7 vàkhông gian cần thiết để giải quyếtmột trường hợp bài toánnhất định. 1.1.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. 1.1.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. 1.1.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 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. 1.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.2.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]. 1.2.2 Đoạn thẳng Một tổ hợp lồi của hai điểm phân biệt một điểm bất kỳ sao cho Đoạn thẳng và . là tập hợp mọi tổ hợp lồi của các điểm đầu mút của đoạn thẳng đoạn thẳng là . Hay viết dưới dạng khác với và và được định hướng từ đến và , kí hiệu , với . Đoạn thẳng có hướng , kí hiệu là [13]. 1.2.3 Vectơ Vectơ là một đoạn thẳng có hướng. Vectơ có điểm đầu được kí hiệu và điểm cuối , . Khi không cần chỉ rõ điểm đầu, điểm cuối ta kí hiệu Tọa độ của vectơ là = với ; [13]. . 1.3 Một số bài toán hình học và thuật toán 1.3.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.3.1.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 9 dọc và không có ba đoạn thẳng nào giao nhau tại một điểm. 1.3.1.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 là có thể so sánh được tại - Nếu và là có thể so sánh tại ở cao hơn với giao điểm của quét tại ở trên tại , kí hiệu và giao điểm của . e g b i c h t với đường thẳng với cùng đường thẳng quét đó thì ta nói d a r nếu đường thẳng quét cắt cả hai đoạn thẳng đó. dọc tại ví trí rằng và f u z v w Hình 1.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ệ , ; Đoạn thẳng và khác, hình 1.1a. Khi đoạn thẳng và , không so sánh được với các đoạn thẳng giao nhau, đường thẳng quét đi qua vùng bóng mờ đều có quan hệ thứ tự , và nhưng ; mọi nằm liên tiếp nhau trong , hình 1.1b. 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. 10 Các thao tác của trình trạng đường thẳng quét - INSERT( ): chèn đoạn thẳng vào . - DELETE( ): xóa đoạn thẳng khỏi . để duy trì truy vấn. - 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 phải nếu có nhiều điểm có cùng tọa độ từ trái sang 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. Output. Cặp các đoạn thẳng trong cắt nhau thì giá trị True, ngược lại là False. 1. 2. 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. 3. for mỗi điểm 4. trong danh sách được sắp xếp của các điểm đầu mút do if là điểm đầu mút trái của đoạn thẳng then 5. INSERT 6. if (ABOVE (BELOW 7. tồn tại và cắt ) hoặc tồn tại và cắt s) then return TRUE 11 if là điểm đầu mút phải của đoạn thẳng then 8. 9. if (ABOVE và (ABOVE 10. 11. và BELOW cắt BELOW đều tồn tại) ) then return TRUE DELETE 12. return FALSE 1.3.1.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-SEGMENTSINTERSECT thực hiện trong thời gian [13]. Thật vậy, dòng1thực hiện mấtthời gian là gian là . Dòng2thực hiện mất thời , bằng cách sử dụngsắp xếp trộn (merge sort) hoặcheapsort. điểm biến cố, vòng lặp forcủadòng3-11thực hiện nhiều nhất là Khicó . , vìmỗihoạt động cây đỏđen mấtthời Mỗilần lặpmất thời gian vàbằng cách sử dụngcácphương phápkiểm tra mỗigiao điểmcần gian thời gian . Vì vậy, thời gianthực hiện thuật toán là . 1.3.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 lồi Bao lồi của tập hợp p không lồi bất kỳ là giao của tất cả các tập lồi chứa bằng trực quan hơn, tập lồi nhỏ nhất chứa , kí hiệu , hay [26]. 1.3.2.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 của hoặc nằm trong phần trong của . hoặc nằm trên biên 12 p10 p10 p11 p9 p11 p9 p7 p6 p5 p4 p8 p2 p12 p3 p12 p8 p7 p6 p5 p4 p3 p2 p1 p1 p0 p0 gồm các điểm và bao lồi Hình 1.2 -Tập hợp 1.3.2.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 đẩylênđầu ngăn xếpvàcác điểmkhông phải làđỉnhcủa ngăn xếpsau xáccácđỉnhcủa cùng. Khithuật toánkết thúc, được được loại bỏ khỏi ngăn xếp chứachính theo thứ tự ngược chiều kimđồng hồ vớisự xuất hiệncủa các điểm trên biên.Thuật toángọihàmTOP( ) - trả vềđiểmtrên cùng củangăn xếp mà không thay đổithứ tự Svàhàm NEXT-TO-TOP( ) - trả vềđiểmtiếp theo trong các điểmdướicùng củangăn xếp mà khôngthay đổithứ tự của . Algorithm GRAHAM-SCAN( ) Input. Tập hợp gồm điểm trong mặt phẳng với Output. Bao lồi của . là 1. Gọi là điểm nằm trong có tọa độ nhỏ nhất hoặc điểm ngoài cùng bên 2. trái trong trường hợp đồng hạng. Gọi là các điểm còn lại trong , sắp xếp theo góc nhọn (polar angle) theo thứ tự ngược chiều kim đồng hồ quanh (nếu có nhiều hơn một điểm có cùng góc thì loại bỏ tất cả nhưng lấy điểm xa nhất từ ). 13 3. PUSH 4. PUSH 5. PUSH 6. for 7. to do while góc tạobởi các điểm NEXT-TO-TOP , TOP và là góc không quay trái do 8. 9. 10. POP PUSH return Thuật toán bước Jarvis [12, 13, 19] Thuật toán bước Jarvis tính toán bao lồi của tập hợp các điểm bởi một kỹ thuật được biết như bọcgói. Trước hết chọn một điểm chắc chắn thuộc bao lồi, giả sử chọn điểm có tọa độ nhỏ nhấttrong . Điểm này là một đỉnh của bao lồi.Sau đótừ kéo cao hơnsang phải cho đến khi chạm vàomột điểm, điểm nàycũng là mộtđỉnhcủabaolồi.Cứ thực hiệntiếp tụcnhư thếtrên tập hợp cácđỉnhcho đến khigặp lạiđỉnhban đầu . Algorithm JARVIS'S MARCH Input. Tập hợp gồm điểm trong mặt phẳng. Output. Bao lồi của . 1. Chọn là một điểm trong tập hợp có tọa độ 2. Chọn là một điểm trong tập hợp mà góc giữa đoạn thẳng nhỏ nhất. với trục hoànhlà nhỏ nhất. 3. Return 4. 5. 6. while Chọn do là điểm trong tập hợp mà góc giữa là lớn nhất. 7. 8. Return 1.3.2.3 Phân tích độ phức tạp Định lí 1.2 Cho tập hợp thuật toán quétGrahamlà gồm điểm trong mặt phẳng. Thời gianthực hiện , trong đó n là số điểm trong [13]. Thật vậy, dòng1chi phíthời gian . Dòng2chi phíthời gian là 14 , bằng cách sử dụngmegersort hoặcheapsortđểsắp xếpcác góc giữa vàphương pháptích có hướng để so sánh các góc. Dòng3-5chi phí thời gian là . Vì , vòng lặp forcủa dòng6-9được thực hiệnnhiều nhất lần. Khi đó thao tác PUSHchi phí thời gian , mỗi lần lặpchi phíthời độc lập vớimất thời gian cho vòng lặpwhile của dòng7-8vàvì thếtoàn gian bộ vònglặp for mấtthời gian chỉ có mộtvòng lặp while lồng nhau. mỗiđiểm được đẩyvàongăn xếp đúng một lần, cónhiều Với nhất một toán tử POPứng vớimỗitoán tử PUSH. Có ít nhấtbađiểm và -là không bao giờlấy rakhỏi ngăn xếp, trongthực tế nhiều nhất toán tử POPđược thực hiệntrong tổng số. Mỗilần lặpwhilemộtPOPthực hiệnvàdo đócónhiều nhất lần lặpwhile. Khithực hiệndòng7với chi phí thời gian , mỗilần gọiPOPvới chi phíthời gian là gianđược thực hiện bởivòng lặpwhile là toán là Định lí 1.3 Cho vàkhi tổng thời . Như vậy, thời gianthực hiệnthuật . là tập hợp gồm thuật toán bước Jarvis là Thật vậy, với điểm trong mặt phẳng. Thời gian thực hiện , trong đó đỉnh của [13]. , tìm đỉnhvớigócgiữa nhỏ nhất.Mỗilần so sánhcác góc giữavới chi phí thời gian là trịtrong thời gian là số đỉnh của bao lồi . Ta có thểtính toánít nhất giá .Như nếumỗi lần so sánhchi phí thời gian là vậy,thuật toán bướcJarvisđược thực hiện với chi phí thời gianlà . 1.3.3 Bài toán tìm cặp điểm gần nhất Bài toán cặp điểm gần nhất tìm hai điểm gần nhất trong tập hợp điểm cho trước.Khoảng cách giữa các điểm thường được xét trong các bài toán hình học khoảng cáchEuclide:khoảng cáchgiữa các điểm và .Mộtthuật toánđơn giản tìm cặpđiểm gần nhấtlàxem là xéttất cả cặpđiểm với chi phí về thời gian là nàysẽmô tảthuật toán chia để trị với chi phí vềthời gian là .Trongphần . 1.3.3.1 Phát biểu bài toán Cho trước tập hợp gồm điểm trong mặt phẳng với đưa ra cặp điểm có khoảng cách nhỏ nhất. 1.3.3.2 Thuật toán và yêu cầu 15 Mỗilời gọiđệ quycủa thuật toáncóđầu vàonhư là tập con và các mảng và ,mỗi mảng có chứatất cả các điểmcủa tập conđầu vào .Các điểm trongmảng được sắp xếptăng dần theo tọa độ , mảng được sắp xếp tăng dầntheotọa độ . Divide:Chiatập hợp các điểm thành hai tập con tọa độ trong ( với điểm giữa của và bởi đường thẳng dọc tất cả , các điểmtrong nằm trênhoặcbên trái củađường thẳng và tất cả các điểm trong nằm mảng và trênhoặc tự,mảng cácđiểmcủa và của .Mảng được phải ,chứacác điểm của và Tương . bên được chia thànhcác tương ứng,sắp xếp tăng dần theo tọa độ chia thànhcác mảng và , chứa tương ứng,sắp xếp tăng dần theotọa độ . Conquer:Tập hợp các điểm được chia thànhhai tập con và ,tạo ra hai lời gọiđệ quymột lời gọi đệ quy tìm cặpđiểmgần nhấttrong vàlời gọi đệ quy .Cácđầu vào củalời gọi đầu tiênlà tập con , khác tìmcặpđiểmgần nhấttrong và ; lời gọi thứ hainhận các đầu vào mảng cáchcặp điểm gần nhấttrả lạicủa và , và tương ứng . Gọicác khoảng là và ;gọi . Combine:Cặp điểmgần nhất hoặc làhaicặpkhoảng cách tìm thấybởimột trong các lời gọi đệ quy,hoặc cặp điểm gần nhất là cặpđiểm vớimột điểm nằm trong và một điểm khácnằm trong .Thuật toánxác địnhkhi cócặpđiểm màkhoảng cáchnhỏ hơn . Nếu có cặpđiểm vớikhoảng cáchnhỏ hơn , cả hai điểmcủa cặpđiểm đó phải đượcnằm trong đơn vị củađường thẳng . - Tạo ra mảng dọc rộng , đó là mảng được loại bỏ. Mảng - Với mỗi điểm trong mảng vị của . Chỉ có 7 điểm trong khoảng cách từ được sắp xếp theo tọa độ , cũng như . , tìm các điểm trong sau được nằm trong đơn cần được xem xét. Thuật toán tính đến mỗi điểm trong 7 điểm đó và theo dõi những khoảng cách cặp điểm gần nhất - Nếu với tất cả các điểm không nằm trong dải đã tìm trên các cặp điểm trong mảng . thì dải dọc thực tế không có một cặp điểm gần hơn đã được tìm thấy bởi các lời gọi đệ quy. Cặp điểm này và khoảng cách của nó được trả về. Ngược lại, cặp gần nhất và khoảng cách của nó được tìm bởi các lời gọi đệ quy được trả về. 16 PR PL pL PR PL các điểm trùng nhau, một trong PL, một trong PR pR các điểm trùng nhau, một trong PL, một trong PR Hình1.3 - Thuật toán chỉ cần kiểm tra điểm trong mảng Algorithm CLOSEST_PAIR( ) Input. Tập hợp gồm các điểm trong mặt phẳng. Output. Cặp điểm gần nhất (cặp điểm có khoảng cách Eulide nhỏ nhất). 1. Chia thành hai tập con và với điểm giữa tọa độ trong bởi đường thẳng dọc ; chia 2. Tìm và ; chia = CLOSEST_PAIR( 3. 4. thành ) và thành và . = CLOSEST_PAIR( ). . Tính khoảng cách giữa các điểm mà một điểm nằm trong điểm nằm trong 4.1 Mảng trong cặp điểm gần nhất 4.3 Nếu )và một thực hiện như sau: - các điểm của 4.2 Với mỗi điểm ( nằm trong dải dọc , chỉ có điểm trong , sắp xếp theo tọa độ . được so sánh, khoảng cách . thì dải dọc thực tế không có một cặp điểm gần hơn đã được tìm thấy bởi các lời gọi đệ quy. Cặp điểm này và khoảng cách của nó được trả về. Ngược lại, cặp điểm gần nhất và khoảng cách của nó được tìm bởi các lời gọi đệ quy được trả về. 5. Return 1.3.3.3 Phân tích độ phức tạp Định lí 1.4Cho tập hợp gồm điểm trong mặt phẳng. Thời gian thực hiện thuật toán tìm cặp điểm gần nhất là Thời gianthực hiện là bảo đảmcác mảng và [13]. . Khó khănchính ở việc được truyền chocác lời gọiđệ quyđược sắp xếp theocáctọa độthích hợp vàcũnglàmảng được sắp xếp theo tọa độ . 17 Trình bàychínhở trongmỗi lời gọi,cầntạo thành mộttập conthứ tựcủa mộtmảng được sắp xếp. Tập hợp được chia thành và ,hình thànhcácmảng được sắp xếp theo tọa độ và . Phương phápnày có thể xem như làđối lậpvới thủ tụcMERGEtừthuật toán sắp xếp trộn (merge sort):chia mảng được sắp xếpthành haimảngđược sắp xếp.Để đơn giản kiểm tra các điểm trongmảng theo thứ tự.Nếumột điểm nằm trong thêm điểm này vàocuốimảng , thêmđiểm này vàocuốimảng ;ngược lại, [13]. 1. 2. for 3. to if do then 4. 5. 6. else 7. Bằng cách nàocó được cácđiểmsắp xếpở vị trí đầu tiên, mộtcách đơn giản làsắp xếp trước chúng.Vì vậy, nếugọi là thời gianthực hiệncủa mỗi bướcđệ làthời gianthực hiện của toàn bộ thuật toán thì nhận được quyvà và Do đó và [13]. 1.4 Kết luận Trong chương này giới thiệu về các vấn đề của hình học tính toán, các đối tượng cơ bản của hình học và các thuật toán kinh điển của hình học tính toán trong không gian hai chiều. Thuật toán xác định cặp đoạn thẳng bất kỳ cắt nhau được đưa ra bởi Shamos và Hoey [28] với độ phức tạp về thời gian là . Thuật toán tìm bao lồi của tập hợp các điểm trong mặt phẳng sử dụng phương pháp quét là thuật toán quét Graham [17] với chi phí thời gian là và thuật toán bước Jarvis [19] với chi phí thời gian là . Có nhiều phương pháp để giải quyết bài toán tìm cặp điểm gần nhất với độ phức tạp khác nhau, sử dụng thuật toán chia để trị tìm cặp điểm gần nhất thì thời gian thực hiện là được đưa ra bởi Shamos và xuất hiện trong Preparata và Shamos [27]. 18 Chương 2 - KIỂU DỮ LIỆU TRỪU TƯỢNG TRONG HÌNH HỌC TÍNH TOÁN 2.1 Tìm kiếm phạm vi trực giao Ngay từ đầu có vẻ nhưcơ sở dữ liệuítlàmviệc vớihình học. Tuy nhiên,nhiềuloại câu hỏi – được gọi là các truy vấn –về dữ liệu trongcơ sở dữ liệucó thểđượcgiải thíchmột cách hình học. Bằng cách chuyển các bản ghitrongcơ sở dữ liệuthành cácđiểmtrongkhông giannhiềuchiềuvàchuyểncác truy vấntrên bản ghithànhcác truy vấntrêntập hợp điểm. Xétmộtcơ sở dữ liệuquản lí nhân sự, mỗi nhân viên được lưu trữ các thông tin như họ tên,địa chỉ, tuổi,lương.Mộttruy vấntạobáo cáotìm tất cả các nhân viêncó tuổi từ 30 đến 50 và thu nhập hàng tháng từ 4000000đến 6000000. Vấn đềhình họcbiểu diễn mỗinhân viênlàmột điểmtrong mặt phẳng.Tọa độ thứ nhất của điểm là tuổivàtọa độ thứ haibiểu diễn lương. Truy vấncơ sở dữ liệuyêu cầu hiển thị tấtcảnhân viêncó tuổi từ 30 đến 50 và thu nhập hàng tháng từ 4000000đến 6000000 được chuyển thành truy vấnhình học: báo cáotất cả cácđiểmvới tọa độthứ nhấttừ 30 đến 50vàtọa độ thứ hai từ 4000000đến 6000000, nghĩa làbáo cáotất cảcácđiểm nằm trongtruy vấnhình chữ nhật song songtrục tọa độ. Lương Nguyễn Thị Lan, 35 tuổi, lương 5000000 6000000 4000000 30 50 Tuổi Hình 2.1- Giải thíchtruy vấncơ sở dữ liệu một cách hình Nếucó thêm thông tinvềsố concủamỗi nhân viênvà yêu cầu tạo truy vấn“báo cáo tất cả nhân viêncó tuổi từ 30 đến 50, thu nhậphàng tháng từ 4000000 đến 6000000 và cótừ 2 đến 4 con”.Trong trường hợpnày,mỗinhân viên