- Một số kiểu dữ liệu trừu tượng ứng dụng trong hình học tính toán. - Abstract: Trình bày các vấn đề cơ bản của hình học tính toán, các đối tượng của hình học và một số kỹ thuật thuật toán giải quyết các bài toán như tìm cặp đoạn thẳng bất kỳ cắt nhau, tìm bao lồi, tìm cặp điểm gần nhất. - Nghiên cứu cơ sở lý thuyết về những cấu trúc dữ liệu để giải quyết các bài toán trong hình học tính toán. - Tìm kiếm phạm vi trực giao với phạm vi truy vấn là hình chữ nhật song song với trục tọa độ sử dụng cấu trúc dữ liệu như Range trees và Kd-trees. - Cấu trúc dữ liệu hình học như Interval trees, Segment trees và Priority search trees trong đó Interval trees, Segment trees dựa trên tiếp cận stabbing và Priority search trees giải quyết các truy vấn không bị giới hạn bên trái, nghĩa là phạm vi truy vấn có dạng. - Biến thể của các cấu trúc dữ liệu hình học như Partition trees, Multi-level partition trees, Cutting trees với phạm vi truy vấn là nửa mặt phẳng hay hình tam giác. - Tiến hành cài đặt thực nghiệm các kiểu dữ liệu trừu tượng như Kd-trees, Range trees, Interval trees và Segment trees.. - Keywords: Cấu trúc dữ liệu. - Hình học tính toán. - 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ờ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.. - 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.. - Chazelle (1986), “Filtering search: A new approach to query-answering”, SIAM J.Comput., 15, pp. - Lett., 1, pp.132-133.. - Comput., 14, pp. - Comput., 11, pp. - ACM Sympos, Theory Comput., pp