On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

Cited In (only showing first 100 items - show all)

Closest-pair queries and minimum-weight queries are equivalent for squares
Sparse geometric graphs with small dilation
An algorithm for generalized point location and its applications
Minimal containment under homothetics: a simple cutting plane approach
A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs
An improved construction for spanners of disks
Routing on heavy-path WSPD-spanners
On the symmetric angle-restricted nearest neighbor problem
Efficient construction of a bounded-degree spanner with low weight
Approximating geometric bottleneck shortest paths
On the angle restricted nearest neighbor problem
Practical methods for shape fitting and kinetic data structures using coresets
Stable roommates spanner
APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS
On computing all north-east nearest neighbors in the $L_ 1$ metric
Fast approximations for sums of distances, clustering and the Fermat-Weber problem
(Weakly) self-approaching geometric graphs and spanners
Approximating nearest neighbor among triangles in convex position
Transitions in geometric minimum spanning trees
Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
Distributed construction of low-interference spanners
On a family of strong geometric spanners that admit local routing strategies
Formal description and analysis of a distributed location service for mobile ad hoc networks
Edge routing with ordered bundles
Approximating the generalized minimum Manhattan network problem
Relative neighborhood graphs in three dimensions
Minimum power assignment in wireless ad hoc networks with spanner property
On path-greedy geometric spanners
Spanners of Additively Weighted Point Sets
A singly exponential stratification scheme for real semi-algebraic varieties and its applications
Empty region graphs
DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS
Approximating the diameter of a set of points in the Euclidean space
Closest-pair queries in fat rectangles
Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces
A simple, faster method for kinetic proximity problems
Geometric spanners with applications in wireless networks
Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications
Reachability problems for transmission graphs
The $\varTheta_5$-graph is a spanner
Selecting distances in the plane
Inner and outer $j$-radii of convex bodies in finite-dimensional normed spaces
Improved local algorithms for spanner construction
The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study
Conic nearest neighbor queries and approximate Voronoi diagrams
Algorithms for proximity problems in higher dimensions
On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces
Local properties of geometric graphs
Minimizing interference of a wireless ad-hoc network in a plane
A sparse graph almost as good as the complete graph on points in $k$ dimensions
π/2-ANGLE YAO GRAPHS ARE SPANNERS
Computing relative neighbourhood graphs in the plane
The region approach for computing relative neighbourhood graphs in the $L_ p$ metric
On the expected maximum degree of Gabriel and Yao graphs
Euclidean minimum spanning trees and bichromatic closest pairs
Constructing the relative neighborhood graph in 3-dimensional Euclidean space
Spanners of additively weighted point sets
Computing Euclidean maximum spanning trees
Title not available (Why is that?)
An O(N log N) minimal spanning tree algorithm for N points in the plane
Efficient minimum spanning tree construction with Delaynay triangulation
Shortest paths in Euclidean graphs
Local edge colouring of Yao-like subgraphs of unit disk graphs
I/O-efficient algorithms for computing planar geometric spanners
The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
Classes of graphs which approximate the complete Euclidean graph
Farthest neighbors, maximum spanning trees and related problems in higher dimensions
Some problems in computational geometry
The Euclidean bottleneck Steiner path problem and other applications of $(\alpha ,\beta )$-pair decomposition
Approximating the minimum closest pair distance and nearest neighbor distances of linearly moving points
Ectropy of diversity measures for populations in Euclidean space
On certain geometric properties of the Yao-Yao graphs
Routing among convex polygonal obstacles in the plane
Routing in polygonal domains
Geometric spanner games
An algorithm for geometric minimum spanning trees requiring nearly linear expected time
Kinetic $k$-semi-Yao graph and its applications
Odd Yao-Yao Graphs are Not Spanners
Spanning Properties of Yao and 𝜃-Graphs in the Presence of Constraints
Spanners for Directed Transmission Graphs
Spanners in randomly weighted graphs: Euclidean case
Spanning properties of Theta-Theta-6
On computing the diameter of a point set in high dimensional Euclidean space.
Truly Optimal Euclidean Spanners
Average case analysis of dynamic geometric optimization
Sigma-local graphs
A simple algorithm for enumerating longest distances in the plane
Minimum weight Euclidean $(1+\varepsilon)$-spanners
Asymptotics of geometrical navigation on a random set of points in the plane
Routing in Polygonal Domains
Routing among convex polygonal obstacles in the plane
An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics
Directional Geometric Routing on Mobile Ad Hoc Networks
Title not available (Why is that?)
Relaxed spanners for directed disk graphs
Self-stabilizing spanner topology control solutions in wireless ad hoc networks
Euclidean Steiner Spanners: Light and Sparse
Improved bounds on the stretch factor of $Y_{4}$
Title not available (Why is that?)
On minimum and maximum spanning trees of linearly moving points

This page was built for publication: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3954830)