期刊
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
卷 48, 期 9, 页码 673-687出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.comgeo.2015.06.008
关键词
Separability; Bichromatic point sets; L-shape
Given a set R of red points and a set B of blue points in the plane, we study the problem of determining all angles for which there exists an L-shape containing all points from B and no points from R. We propose a worst-case optimal algorithm to solve this problem in O(n(2)) time and O(n) storage, where n = vertical bar R vertical bar + vertical bar B vertical bar. We also describe an output-sensitive algorithm that reports these angles in O(n(8/5+epsilon) klogk) time and O(n(8/5+epsilon)) storage, where k is the number of reported angular intervals and epsilon > 0 is any fixed constant. (C) 2015 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据