کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6875503 1441960 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Planar maximum-box problem revisited
ترجمه فارسی عنوان
مسأله بزرگترین جعبه مسطح مجددا بررسی شد
کلمات کلیدی
بهینه سازی گسسته، هندسه محاسباتی، الگوریتم های جاروب کردن هواپیما،
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Let B be a set of b blue points and R be a set of r red points in the plane. In this paper we study the problem of finding rectangles that contain the maximum number of blue points without containing any red points, known as the maximum-box problem. First we study this problem for axis-aligned rectangles, and propose an exact worst-case optimal O(r2+rb+blog⁡b) time algorithm using O(r+b) space to find all maximum boxes. We also provide a 2-approximation algorithm running in O((r+b)log⁡(r+b)) time and using O(r+b) space to find a single maximum box in the axis-aligned case. Then we generalize the exact algorithm for the axis-aligned case to find all arbitrarily oriented maximum boxes leading to a worst-case optimal O((r+b)2(r+log⁡b)) time algorithm using O((r+b)2) space to solve the problem. We conclude the paper by discussing time and space trade-offs. Our results improve the previously best known solutions to the maximum-box problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 729, 12 June 2018, Pages 57-67
نویسندگان
, ,