Yuichiro Miyamoto   Takeaki Uno   Mikio Kubo   
ALGORITHMS AND COMPUTATION, PT I 6506 121-+ 2010年
In this paper, we address the shortest path query problem, i.e., constructing a data structure of a given network to answer the shortest path length of two given points in a short time. We present a method named Levelwise Mesh Sparsification for t...
Given a finite set of 2-dimensional points P c R 2 and a positive real d, a unit disk graph, denoted by (P. d), is an undirected graph with vertex set P such that two vertices are adjacent if and only if the Euclidean distance between the pair is ...
Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012 241-246 2012年12月
This paper discusses a problem for determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangula- Tion. There exists a theorem which characterizes De- launay graphs and yields a p...