Separating bichromatic point sets in the plane by restricted orientation convex hulls
CC By
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Sách |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Springer
2023
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s10898-022-01238-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7427 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| id |
oai:localhost:PNK-7427 |
|---|---|
| record_format |
dspace |
| spelling |
oai:localhost:PNK-74272023-04-03T04:07:53Z Separating bichromatic point sets in the plane by restricted orientation convex hulls Carlos, Alegría David, Orden Carlos, Seara O(nlogn) time and O(n) space n=|R|+|B| CC By We explore the separability of point sets in the plane by a restricted-orientation convex hull, which is an orientation-dependent, possibly disconnected, and non-convex enclosing shape that generalizes the convex hull. Let R and B be two disjoint sets of red and blue points in the plane, and O be a set of k≥2 lines passing through the origin. We study the problem of computing the set of orientations of the lines of O for which the O-convex hull of R contains no points of B. For k=2 orthogonal lines we have the rectilinear convex hull. In optimal O(nlogn) time and O(n) space, n=|R|+|B|, we compute the set of rotation angles such that, after simultaneously rotating the lines of O around the origin in the same direction, the rectilinear convex hull of R contains no points of B. 2023-04-03T04:07:53Z 2023-04-03T04:07:53Z 2022 Book https://link.springer.com/article/10.1007/s10898-022-01238-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7427 en application/pdf Springer |
| institution |
Digital Phenikaa |
| collection |
Digital Phenikaa |
| language |
English |
| topic |
O(nlogn) time and O(n) space n=|R|+|B| |
| spellingShingle |
O(nlogn) time and O(n) space n=|R|+|B| Carlos, Alegría David, Orden Carlos, Seara Separating bichromatic point sets in the plane by restricted orientation convex hulls |
| description |
CC By |
| format |
Book |
| author |
Carlos, Alegría David, Orden Carlos, Seara |
| author_facet |
Carlos, Alegría David, Orden Carlos, Seara |
| author_sort |
Carlos, Alegría |
| title |
Separating bichromatic point sets in the plane by restricted orientation convex hulls |
| title_short |
Separating bichromatic point sets in the plane by restricted orientation convex hulls |
| title_full |
Separating bichromatic point sets in the plane by restricted orientation convex hulls |
| title_fullStr |
Separating bichromatic point sets in the plane by restricted orientation convex hulls |
| title_full_unstemmed |
Separating bichromatic point sets in the plane by restricted orientation convex hulls |
| title_sort |
separating bichromatic point sets in the plane by restricted orientation convex hulls |
| publisher |
Springer |
| publishDate |
2023 |
| url |
https://link.springer.com/article/10.1007/s10898-022-01238-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7427 |
| _version_ |
1762184302801453056 |
| score |
8.881002 |