排序方式: 共有3条查询结果,搜索用时 0 毫秒
1
1.
Miller Kim Ramaswami Suneeta Rousseeuw Peter Sellarès J. Antoni Souvaine Diane Streinu Ileana Struyf Anja 《Statistics and Computing》2003,13(2):153-162
The concept of location depth was introduced as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust estimation, hypothesis testing, and graphical display. The depth contours form a collection of nested polygons, and the center of the deepest contour is called the Tukey median. The only available implemented algorithms for the depth contours and the Tukey median are slow, which limits their usefulness. In this paper we describe an optimal algorithm which computes all bivariate depth contours in O(n
2) time and space, using topological sweep of the dual arrangement of lines. Once these contours are known, the location depth of any point can be computed in O(log2
n) time with no additional preprocessing or in O(log n) time after O(n
2) preprocessing. We provide fast implementations of these algorithms to allow their use in everyday statistical practice. 相似文献
2.
Marwan Al-Jubeh Michael Hoffmann Mashhood Ishaque Diane L. Souvaine Csaba D. Tóth 《Journal of Combinatorial Optimization》2011,22(3):409-425
It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be partitioned into open convex cells whose dual graph (defined below)
is 2-edge connected. Intuitively, every edge of the dual graph corresponds to a pair of adjacent cells that are both incident
to the same vertex. 相似文献
3.
Brad Ballinger Nadia Benbernou Prosenjit Bose Mirela Damian Erik D. Demaine Vida Dujmović Robin Flatland Ferran Hurtado John Iacono Anna Lubiw Pat Morin Vera Sacristán Diane Souvaine Ryuhei Uehara 《Journal of Combinatorial Optimization》2013,25(2):208-233
For a fixed integer k≥0, a k-transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k “walls”, represented as line segments in the plane. We develop lower and upper bounds for the number of k-transmitters that are necessary and sufficient to cover a given collection of line segments, polygonal chains and polygons. 相似文献
1