ConferenceDiscrete and Computational Geometry · September 1, 2024
Let C be a set of n axis-aligned cubes of arbitrary sizes in R3 in general position. Let U:=U(C) be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and Θ(n2). We present a partition of cl(R3\U) into O(κlog4n) axis-aligned bo ...
Full textCite
ConferenceProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms · January 1, 2024
Let W ⊂ R2 be a planar polygonal environment (i.e., a polygon potentially with holes) with a total of n vertices, and let A, B be two robots, each modeled as an axis-aligned unit square, that can translate inside W. Given source and target placements sA, t ...
Full textCite
ConferenceLeibniz International Proceedings in Informatics, LIPIcs · July 1, 2021
Let C be a set of n axis-aligned cubes of arbitrary sizes in ℝ3. Let U be their union, and let κ be the number of vertices on ∂U; κ can vary between O(1) and O(n2). We show that U can be computed in O(n log3 n + κ) time if C is in general position. The alg ...
Full textCite
ConferenceProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems · June 14, 2020
Let P be a set of n (non-negatively) weighted points in Rd. We consider the problem of computing a subset of (at most) k diverse and high-valued points of P that lie inside a query range, a problem relevant to many areas such as search engines, recommendat ...
Full textCite
