1. Trang chủ
  2. » Luận Văn - Báo Cáo

Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn

121 13 0

Đang tải... (xem toàn văn)

Tài liệu hạn chế xem trước, để xem đầy đủ mời bạn chọn Tải xuống

THÔNG TIN TÀI LIỆU

Thông tin cơ bản

Tiêu đề Bài Toán Tìm Bao Lồi Của Tập Hữu Hạn Các Điểm Hoặc Các Hình Tròn
Tác giả Nguyễn Kiều Linh
Người hướng dẫn TS. Hoàng Nam Dũng, PGS. TS. Phan Thành An
Trường học Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
Chuyên ngành Toán ứng dụng
Thể loại luận án tiến sĩ toán học
Năm xuất bản 2019
Thành phố Hà Nội
Định dạng
Số trang 121
Dung lượng 4,18 MB

Nội dung

Ngày đăng: 03/07/2021, 09:03

Nguồn tham khảo

Tài liệu tham khảo Loại Chi tiết
[1] Nguyễn Văn Hiền, Lê Dũng Mưu, Nguyễn Hữu Điển (2014), Giáo trình Giải tích lồi ứng dụng, NXB Đại học Quốc gia Hà Nội, Hà Nội Sách, tạp chí
Tiêu đề: Giáo trình Giải tích lồi ứng dụng
Tác giả: Nguyễn Văn Hiền, Lê Dũng Mưu, Nguyễn Hữu Điển
Nhà XB: NXB Đại học Quốc gia Hà Nội
Năm: 2014
[2] Trần Bình Nguyên (2011), Hệ thống nhận diện biển số xe,http://www.ieev.org/2011/01/tong-quan-ve-he-thong-nhan-dien-bang-so. html#comment-post-messageTiếng Anh Sách, tạp chí
Tiêu đề: Hệ thống nhận diện biển số xe
Tác giả: Trần Bình Nguyên
Năm: 2011
[3] S. G. Akl and G. T. Toussaint (1978), “Efficient convex hull algorithms for pat- tern recognition applications”, International Conference on Pattern Recognition, Kyoto, Japan, pp. 483–487 Sách, tạp chí
Tiêu đề: Efficient convex hull algorithms for pat- tern recognition applications
Tác giả: S. G. Akl, G. T. Toussaint
Nhà XB: International Conference on Pattern Recognition
Năm: 1978
[6] P. T. An and T. V. Hoai (2012), “Incremental convex hull as an orientation to solving the shortest path problem”, International Journal of Information and Electronics Engineering 2(5), pp. 652–655 Sách, tạp chí
Tiêu đề: Incremental convex hull as an orientation to solving the shortest path problem
Tác giả: P. T. An, T. V. Hoai
Nhà XB: International Journal of Information and Electronics Engineering
Năm: 2012
[8] P. T. An and L. H. Trang (2013), “An efficient convex hull algorithm for finite point sets in 3D based on the method of orienting curves”, Optimization 62, pp.975–988 Sách, tạp chí
Tiêu đề: An efficient convex hull algorithm for finite point sets in 3D based on the method of orienting curves
Tác giả: P. T. An, L. H. Trang
Nhà XB: Optimization
Năm: 2013
[9] F. Aurenhammer, R. Klein, and D. Lee (2013), “Voronoi diagrams and delaunay riangulations”, World Scientific Publishing Co. Pte. Ltd Sách, tạp chí
Tiêu đề: Voronoi diagrams and delaunay riangulations
Tác giả: F. Aurenhammer, R. Klein, D. Lee
Nhà XB: World Scientific Publishing Co. Pte. Ltd
Năm: 2013
[10] C. B. Barber, D. P. Dobkin, and H. Huhdanpaa (1996),“The quickhull algorithm for convex hulls", University of Minnesota Sách, tạp chí
Tiêu đề: The quickhull algorithm for convex hulls
Tác giả: C. B. Barber, D. P. Dobkin, H. Huhdanpaa
Nhà XB: University of Minnesota
Năm: 1996
[11] J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson (1978), “On the average number of maxima in a set of vectors and application”, Journal of the Association for Computing Machinery 25(4), pp. 536–543 Sách, tạp chí
Tiêu đề: On the average number of maxima in a set of vectors and application
Tác giả: J. L. Bentley, H. T. Kung, M. Schkolnick, C. D. Thompson
Nhà XB: Journal of the Association for Computing Machinery
Năm: 1978
[12] P. Bhaniramka, R. Wenger and R. Crawfis (2004), “Isosurface construction in any dimension using convex hulls”, IEEE Transactions on Visualization and Com- puter Graphics 10(2), pp. 130–141 Sách, tạp chí
Tiêu đề: Isosurface construction in anydimension using convex hulls
Tác giả: P. Bhaniramka, R. Wenger and R. Crawfis
Năm: 2004
[13] B. Bhattacharya (1982), “Worst-case analysis of a convex hull algorithm, Depart- ment of Computer Science, Simon Fraser University”, Unpublished manuscript Sách, tạp chí
Tiêu đề: Worst-case analysis of a convex hull algorithm
Tác giả: B. Bhattacharya
Nhà XB: Department of Computer Science, Simon Fraser University
Năm: 1982
[14] P. Bolstad (2002), “GIS Fundamentals: A First Text on Geographic Information Systems”, White Bear Lake, Minnesota: Eider Press Sách, tạp chí
Tiêu đề: GIS Fundamentals: A First Text on Geographic Information Systems
Tác giả: P. Bolstad
Nhà XB: Eider Press
Năm: 2002
[15] S. Boyd and L. Vandenberghe (2004), Convex optimization, Cambridge Univer- sity Press Sách, tạp chí
Tiêu đề: Convex optimization
Tác giả: S. Boyd, L. Vandenberghe
Nhà XB: Cambridge University Press
Năm: 2004
[16] D. R. Chand and S. S. Kapur (1970), “An algorithm for convex polytopes”, Journal of the ACM 1, pp. 78–86 Sách, tạp chí
Tiêu đề: An algorithm for convex polytopes
Tác giả: D. R. Chand, S. S. Kapur
Nhà XB: Journal of the ACM
Năm: 1970
[17] T. M. Chan (1996), Optimal output-sensitive convex hull algorithms in two and three dimensions, Discrete & Computational Geometry, pp. 361–368 Sách, tạp chí
Tiêu đề: Optimal output-sensitive convex hull algorithms in two and three dimensions
Tác giả: T. M. Chan
Nhà XB: Discrete & Computational Geometry
Năm: 1996
[18] W. Chen, K. Wada, K. Kawaguchi, and D. Z. Chen (1998), “Finding the convex hull of discs in parallel”, International Journal of Computational Geometry &Applications 3, pp. 305–319 Sách, tạp chí
Tiêu đề: Finding the convexhull of discs in parallel
Tác giả: W. Chen, K. Wada, K. Kawaguchi, and D. Z. Chen
Năm: 1998
[19] V. Damerow and C. Sohler (2004), “Extreme points under random noise”, Ero- pean Symposium on Algorithms 3221, pp. 264–274 Sách, tạp chí
Tiêu đề: Extreme points under random noise
Tác giả: V. Damerow and C. Sohler
Năm: 2004
[20] M. M. David (2002), Computation geometry, Department of Computer Science Sách, tạp chí
Tiêu đề: Computation geometry
Tác giả: M. M. David
Nhà XB: Department of Computer Science
Năm: 2002
[21] N. Dinh and H. X. Phu (1992), “Solving a class of regular optimal control prob- lems with state constraints by the method of orienting curves”, Optimization 25, pp. 231–247 Sách, tạp chí
Tiêu đề: Solving a class of regular optimal control problems with state constraints by the method of orienting curves
Tác giả: N. Dinh, H. X. Phu
Nhà XB: Optimization
Năm: 1992
[22] N. Dinh and H. X. Phu (1992), “Solving a class of optimal control problems which are linear in the control variable by the method of orienting curves”, Acta Mathematica Vietnamica 17, pp. 115–134 Sách, tạp chí
Tiêu đề: Solving a class of optimal control problems which are linear in the control variable by the method of orienting curves
Tác giả: N. Dinh, H. X. Phu
Nhà XB: Acta Mathematica Vietnamica
Năm: 1992
[23] R. L. Graham (1972), “An efficient algorithm for determining the convex hull of a finite planar set”, Information Processing Letters 1 , pp. 132–133 Sách, tạp chí
Tiêu đề: An efficient algorithm for determining the convex hull ofa finite planar set
Tác giả: R. L. Graham
Năm: 1972

HÌNH ẢNH LIÊN QUAN

Hình 1.2 Bao lồi của tập điểm trong không gian R2. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 1.2 Bao lồi của tập điểm trong không gian R2 (Trang 21)
Hình 1.4 Quy trình tự động nhận dạng biển số xe. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 1.4 Quy trình tự động nhận dạng biển số xe (Trang 26)
Hình 1.7 Trích vùng biển số xe. Hình 1.8 Tìm bao lồi cho mỗi kí tự. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 1.7 Trích vùng biển số xe. Hình 1.8 Tìm bao lồi cho mỗi kí tự (Trang 27)
Hình 1.21 Bài toán gói cáp (cable packing problem). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 1.21 Bài toán gói cáp (cable packing problem) (Trang 35)
Hình 2.1 Thuật toán Quickhull. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.1 Thuật toán Quickhull (Trang 40)
Hình 2.5 Trường hợp px ≤ rx ≤ q x. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.5 Trường hợp px ≤ rx ≤ q x (Trang 45)
Hình 2.7 Bốn tập điểm Q 1, Q2, Q3vàQ4. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.7 Bốn tập điểm Q 1, Q2, Q3vàQ4 (Trang 46)
Hình 2.9 Năm kiểu dữ liệu. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.9 Năm kiểu dữ liệu (Trang 50)
Bảng 2.1 So sánh hệ số tăng tốc của bốn phiên bản Quickhull so với thuật toán Quickhull ban đầu. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 2.1 So sánh hệ số tăng tốc của bốn phiên bản Quickhull so với thuật toán Quickhull ban đầu (Trang 51)
Hình 2.10 Minh họa kết quả tính toán của năm kiểu dữ liệu 10.000 điểm. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.10 Minh họa kết quả tính toán của năm kiểu dữ liệu 10.000 điểm (Trang 52)
Hình 2.11 Diện tích giới hạntrênsiêuphẳngtọa độ Ox 1x2. . . xd−1. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.11 Diện tích giới hạntrênsiêuphẳngtọa độ Ox 1x2. . . xd−1 (Trang 55)
Hình 2.14 Miền hạn chế của siêu phẳng (a1a2 t) trên Ox1x2 được giới thiệu bởi An và Trang trong [8]. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.14 Miền hạn chế của siêu phẳng (a1a2 t) trên Ox1x2 được giới thiệu bởi An và Trang trong [8] (Trang 56)
Hình 2.15 Tỉ số diện tích giới hạn của (a1a2. . . ad−1t)trên Ox 1x2. . . xd−1. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.15 Tỉ số diện tích giới hạn của (a1a2. . . ad−1t)trên Ox 1x2. . . xd−1 (Trang 59)
trong hình tròn - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
trong hình tròn (Trang 63)
Hình 2.18 Đồ thị so sánh thời gian chạy của thuật toán gói quà và Thuật toán 2.9 cho dữ liệu trong hình vuông. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 2.18 Đồ thị so sánh thời gian chạy của thuật toán gói quà và Thuật toán 2.9 cho dữ liệu trong hình vuông (Trang 64)
Bảng 2.3 Thời gian tính bao lồi với dữ liệu trong hình tròn (đơn vị: giây). Đầu vào |conv(P)|Gói quàThuật toán 2.9Tỉ số tăng tốc - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 2.3 Thời gian tính bao lồi với dữ liệu trong hình tròn (đơn vị: giây). Đầu vào |conv(P)|Gói quàThuật toán 2.9Tỉ số tăng tốc (Trang 64)
Bảng 2.5 Thời gian tính bao lồi với kiểu dữ liệu trên mặt cầu (đơn vị: giây). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 2.5 Thời gian tính bao lồi với kiểu dữ liệu trên mặt cầu (đơn vị: giây) (Trang 65)
Bảng 2.4 Thời gian tính bao lồi cho kiểu dữ liệu tạo trong hình lập phương (đơn vị: giây). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 2.4 Thời gian tính bao lồi cho kiểu dữ liệu tạo trong hình lập phương (đơn vị: giây) (Trang 65)
Ta ký hiệu ∂(d) là biên của hình tròn d. Để đơn giản, khi ta viết “hình tròn dđi qua điểmq” có nghĩa là “hình tròndcó biên∂(d)đi qua điểmq”. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
a ký hiệu ∂(d) là biên của hình tròn d. Để đơn giản, khi ta viết “hình tròn dđi qua điểmq” có nghĩa là “hình tròndcó biên∂(d)đi qua điểmq” (Trang 72)
ii. Nếu nhiễu ngẫu nhiên được chọn từ phân bố đều trong hình vuông kích thước 2, tức là - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
ii. Nếu nhiễu ngẫu nhiên được chọn từ phân bố đều trong hình vuông kích thước 2, tức là (Trang 88)
Dữ liệu hình tròn rỗng: Trong các ví dụ của kiểu dữ liệu này chúng tôi tạo hai đường tròn (hoặc elipse) có bán kính khác nhau - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
li ệu hình tròn rỗng: Trong các ví dụ của kiểu dữ liệu này chúng tôi tạo hai đường tròn (hoặc elipse) có bán kính khác nhau (Trang 91)
Hình tròn rỗng - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình tr òn rỗng (Trang 93)
Bảng 4.1 Thời gian tính toán cho tập D1 (đơn vị: giây). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 4.1 Thời gian tính toán cho tập D1 (đơn vị: giây) (Trang 102)
Bảng 4.2 Thời gian tính toán cho tập D2 (đơn vị: giây). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 4.2 Thời gian tính toán cho tập D2 (đơn vị: giây) (Trang 102)
Bảng 4.4 Thời gian tính toán cho tập D4 (đơn vị: giây). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 4.4 Thời gian tính toán cho tập D4 (đơn vị: giây) (Trang 103)
Bảng 4.3 Thời gian tính toán cho tập D3 (đơn vị: giây). - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 4.3 Thời gian tính toán cho tập D3 (đơn vị: giây) (Trang 103)
Bởi vậy hình chiếu t0 (tx ,t y) của t(tx ,t y, t z) thuộc (C1) với (C1) là đường tròn có tâm q(q x, qy)và bán kínhr1> cq+rhayr1 −r > cq - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
i vậy hình chiếu t0 (tx ,t y) của t(tx ,t y, t z) thuộc (C1) với (C1) là đường tròn có tâm q(q x, qy)và bán kínhr1> cq+rhayr1 −r > cq (Trang 111)
Hình 4.5 Đồ thị so sánh thời gian chạy tính bao lồi dưới của thuật toán trong [7] và Thuật toán 4.4. - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Hình 4.5 Đồ thị so sánh thời gian chạy tính bao lồi dưới của thuật toán trong [7] và Thuật toán 4.4 (Trang 113)
Bảng 4.5 Thời gian chạy tính bao lồi dưới (đơn vị: giây). Đầu vàoThuật toán trong [7]Thuật toán 4.4 Tỉ số thăng tốc - Bài toán tìm bao lồi của tập hữu hạn các điểm hoặc các hình tròn
Bảng 4.5 Thời gian chạy tính bao lồi dưới (đơn vị: giây). Đầu vàoThuật toán trong [7]Thuật toán 4.4 Tỉ số thăng tốc (Trang 113)

TÀI LIỆU CÙNG NGƯỜI DÙNG

TÀI LIỆU LIÊN QUAN

w