PHAG
发表于 2025-3-30 10:31:27
Simon Forstmeier,Andreas Maerckern optimal search tree using 2-way comparisons remained open — poly-time algorithms were known only for restricted variants. We solve the general case, giving (i) an .-time algorithm and (ii) an .-time additive-3 approximation algorithm. For finding optimal ., we (iii) obtain a linear speedup and (iv) prove some previous work incorrect.
llibretto
发表于 2025-3-30 12:29:09
Adaptive Point Location in Planar Convex Subdivisions location queries in .. The running time includes the preprocessing time. Therefore, for ., our running time is only worse than the best possible bound by . per query, which is much smaller than the . query time offered by an worst-case optimal planar point location structure.
是突袭
发表于 2025-3-30 17:58:03
Navigating Weighted Regions with Scattered Skinny Tetrahedra be some arbitrary constant. Let . be the size of the largest connected component of tetrahedra whose aspect ratios exceed .. There exists a constant . dependent on . but independent of . such that if ., the running time of our algorithm is polynomial in ., . and .. If ., the running time reduces to ..
付出
发表于 2025-3-30 23:41:59
Optimal Search Trees with 2-Way Comparisonsn optimal search tree using 2-way comparisons remained open — poly-time algorithms were known only for restricted variants. We solve the general case, giving (i) an .-time algorithm and (ii) an .-time additive-3 approximation algorithm. For finding optimal ., we (iii) obtain a linear speedup and (iv) prove some previous work incorrect.