In this paper, we study two extensions of the maximum bichromatic separating rectangle (MBSR) problem introduced in \cite{Armaselu-CCCG, Armaselu-arXiv}. One of the extensions, introduced in \cite{Armaselu-FWCG}, is called \textit{MBSR with outliers} or MBSR-O, and is a more general version of the MBSR problem in which the optimal rectangle is allowed to contain up to $k$ outliers, where $k$ is given as part of the input. For MBSR-O, we improve the previous known running time bounds of $O(k^7 m \log m + n)$ to $O(k^3 m + m \log m + n)$. The other extension is called \textit{MBSR among circles} or MBSR-C and asks for the largest axis-aligned rectangle separating red points from blue unit circles. For MBSR-C, we provide an algorithm that runs in $O(m^2 + n)$ time.


翻译:在本文中,我们研究了在\ cite{ Armaslu-CCCG, Armaslu-arXiv} 中引入的最大双色分离矩形(MBSR)问题的两个延伸。 在\ cite{Armaslu-FWCG} 中引入的一个扩展名为\ textit{MBSR with extliers} 或 MBSR-O, 是MBSR问题的一个更普通的版本, 允许最佳矩形包含最多为$k$的外端, 以美元作为输入的一部分。 对于 MBSR- O, 我们将已知的$( kä7 m log m + n) 的运行时间范围改进为$( kä3 m + m log m + n) $( k) 。 另一个扩展名为\ textitit{MBSR- C 或 MBSR- C, 并请求使用最大轴- 轴矩形红点分隔于蓝色单元圈的红点。 对于 MBSR- C, 我们提供一种以 $ time.

0
下载
关闭预览

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
  • Today (iOS and OS X): widgets for the Today view of Notification Center
  • Share (iOS and OS X): post content to web services or share content with others
  • Actions (iOS and OS X): app extensions to view or manipulate inside another app
  • Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
  • Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
  • Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
  • Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
【NYU-WESLEY MADDOX】贝叶斯神经网络教程,83页ppt
专知会员服务
59+阅读 · 2021年4月15日
专知会员服务
50+阅读 · 2020年12月14日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
已删除
将门创投
8+阅读 · 2019年6月13日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】直接未来预测:增强学习监督学习
机器学习研究会
6+阅读 · 2017年11月24日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年8月27日
Arxiv
0+阅读 · 2021年8月26日
Non-Parametric Quickest Mean Change Detection
Arxiv
0+阅读 · 2021年8月25日
Arxiv
0+阅读 · 2021年8月24日
Arxiv
11+阅读 · 2020年12月2日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关VIP内容
【NYU-WESLEY MADDOX】贝叶斯神经网络教程,83页ppt
专知会员服务
59+阅读 · 2021年4月15日
专知会员服务
50+阅读 · 2020年12月14日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
8+阅读 · 2019年6月13日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】直接未来预测:增强学习监督学习
机器学习研究会
6+阅读 · 2017年11月24日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】RNN/LSTM时序预测
机器学习研究会
25+阅读 · 2017年9月8日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
相关论文
Arxiv
0+阅读 · 2021年8月27日
Arxiv
0+阅读 · 2021年8月26日
Non-Parametric Quickest Mean Change Detection
Arxiv
0+阅读 · 2021年8月25日
Arxiv
0+阅读 · 2021年8月24日
Arxiv
11+阅读 · 2020年12月2日
Arxiv
3+阅读 · 2018年2月24日
Top
微信扫码咨询专知VIP会员