Cover Image

Separating bichromatic point sets in the plane by restricted orientation convex hulls

CC By

Saved in:
Bibliographic Details
Main Authors: Carlos, Alegría, David, Orden, Carlos, Seara
Format: Book
Language:English
Published: Springer 2023
Subjects:
O(nlogn) time and O(n) space
n=|R|+|B|
Online Access:https://link.springer.com/article/10.1007/s10898-022-01238-9
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7427
Tags: Add Tag
No Tags, Be the first to tag this record!
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.891787

Similar Items