Zobrazeno 1 - 10
of 635
pro vyhledávání: '"randomized incremental construction"'
The Randomized Incremental Construction (RIC) of search DAGs for point location in planar subdivisions, nearest-neighbor search in 2D points, and extreme point search in 3D convex hulls, are well known to take ${\cal O}(n \log n)$ expected time for s
Externí odkaz:
http://arxiv.org/abs/2101.04914
Autor:
Sen, Sandeep
By combining several interesting applications of random sampling in geometric algorithms like point location, linear programming, segment intersections, binary space partitioning, Clarkson and Shor \cite{CS89} developed a general framework of randomi
Externí odkaz:
http://arxiv.org/abs/1808.02356
Net-trees are a general purpose data structure for metric data that have been used to solve a wide range of algorithmic problems. We give a simple randomized algorithm to construct net-trees on doubling metrics using $O(n\log n)$ time in expectation.
Externí odkaz:
http://arxiv.org/abs/1809.01308
This paper applies the randomized incremental construction (RIC) framework to computing the Hausdorff Voronoi diagram of a family of k clusters of points in the plane. The total number of points is n. The diagram is a generalization of Voronoi diagra
Externí odkaz:
http://arxiv.org/abs/1612.01335
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Given a planar map of $n$ segments in which we wish to efficiently locate points, we present the first randomized incremental construction of the well-known trapezoidal-map search-structure that only requires expected $O(n \log n)$ preprocessing time
Externí odkaz:
http://arxiv.org/abs/1410.5602
Publikováno v:
In Computational Geometry: Theory and Applications October 2016 58:110-123
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
In the Hausdorff Voronoi diagram of a set of clusters of points in the plane, the distance between a point t and a cluster P is the maximum Euclidean distance between t and a point in P. This diagram has direct applications in VLSI design. We conside
Externí odkaz:
http://arxiv.org/abs/1306.5838
Autor:
Har-Peled, Sariel
We present a simple randomized incremental algorithm for building compressed quadtrees. The resulting algorithm seems to be simpler than previously known algorithms for this task.
Externí odkaz:
http://arxiv.org/abs/0907.0907