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

Nguyễn Thị Hoa

Trường Đại học Công nghệ
Luận văn Thạc sĩ ngành: Hệ thống thông tin; Mã số: 60 48 05
Người hướng dẫn: TS. Lê Minh Hoàng
Năm bảo vệ: 2011

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; Công nghệ thông tin; Hệ thống
thông tin

Content
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

2. J. L. Bentley (1975), “Multidimensional binary search trees used for associative
searching”, Commun. ACM, 18, pp. 509-517.
3. J. L. Bentley (1977), “Solutions to Klee’s rectangle problems”, Technical report,
Carnegie-Mellon Univ., Pittsburgh, PA.
4. J. L. Bentley (1979), “Decomposable searching problems”, Inform. Process. Lett., 8, pp.
244-251.
5. M. de Berg, O. Cheong, M. van Kreveld, M. Overmars (2000), Computational
Geometry: algorithms and applications, Springer.
6. B. Chazelle (1986), “Filtering search: A new approach to query-answering”, SIAM
J.Comput., 15, pp. 703-724.
7. B. Chazelle (1989), “Lower bounds on the complexity of polytope range searching”, J.
Amer. Math. Soc., 2, pp. 637-666.
8. B. Chazelle (1993), “Cutting hyperplanes for divide-and-conquer”, Discrete Comput.
Geom., 9, pp. 145-158.
9. B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir (1994), “Algorithms for
bichromatic line segment problems and polyhedral terrains”, Algorithmica, 11, pp. 116-
132.
10. B. Chazelle, M. Sharir, and E. Welzl (1992), “Quasi-optimal upper bounds for simplex

3
range searching and new zone theorems”, Algorithmica, 8, pp. 407-429.
11. B. Chazelle and E. Welzl (1989), “Quasi-optimal range searching in spaces of finite VC-
dimension”, Discrete Comput. Geom., 4, pp. 467-489.
12. J. Chen (1996), Computational Geometry: Methods and applications, Computer
Science Department, Texas A&M University.
13. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (2001), Introduction to
Algorithms, Second Edition, MIT Press, Cambridge.
14. H. Edelsbrunner (1980), “Dynamic data structures for orthogonal intersection queries”,
Report F59, Inst. Informationsverarb., Tech. Univ. Graz, Graz, Austria.
15. H. Edelsbrunner and H. A. Maurer (1981), “On the intersection of orthogonal objects”,

problems”, In Proc. 4th Annu. ACM Sympos. Comput. Geom., pp. 23-33.
31. D. E. Willard (1978), Predicate-Oriented Database Search Algorithms, Ph.D. thesis,
Aiken Comput. Lab., Harvard Univ., Cambridge, MA.
32. D. E. Willard (1982), “Polygon retrieval”, SIAM J. Comput., 11, pp. 149-165.
33. A. C. Yao and F. F. Yao (1985), “A general approach to D-dimensional geometric
queries”, In Proc. 17th Annu. ACM Sympos, Theory Comput., pp. 163-168.
34.