Computing generalized higher-order Voronoi diagrams on triangulated surfaces

We present an algorithm for computing exact shortest paths, and consequently distance functions, from a generalized source (point, segment, polygonal chain or polygonal region) on a possibly non-convex triangulated polyhedral surface. The algorithm is generalized to the case when a set of generalized sites is considered, providing their distance field that implicitly represents the Voronoi diagram of the sites. Next, we present an algorithm to compute a discrete representation of the distance function and the distance field. Then, by using the discrete distance field, we obtain the Voronoi diagram of a set of generalized sites (points, segments, polygonal chains or polygons) and visualize it on the triangulated surface. We also provide algorithms that, by using the discrete distance functions, provide the closest, furthest and k-order Voronoi diagrams and an approximate 1-Center and 1-Median.     

Stable marker-particle method for the Voronoi diagram in a flow field

The Voronoi diagram in a flow field is a tessellation of water surface into regions according to the nearest island in the sense of a “boat-sail distance”, which is a mathematical model of the shortest time for a boat to move from one point to another against the flow of water. The computation of the diagram is not easy, because the equi-distance curves have singularities. To overcome the difficulty, this paper derives a new system of equations that describes the motion of a particle along the shortest path starting at a given point on the boundary of an island, and thus gives a new variant of the marker-particle method. In the proposed method, each particle can be traced independently, and hence the computation can be done stably even though the equi-distance curves have singular points.     

Some theoretical challenges in digital geometry: A perspective

In recent years image analysis has become a research field of exceptional significance, due to its relevance to real life problems in important societal and governmental sectors, such as medicine, defense, and security. The explicit purpose of the present Perspective is to suggest a number of strategic objectives for theoretical research, with an emphasis on the combinatorial approach in image analysis. Most of the proposed objectives relate to the need to make the theoretical foundations of combinatorial image analysis better integrated within a number of well-established subjects of theoretical computer science and discrete applied mathematics, such as the theory of algorithms and problem complexity, combinatorial optimization and polyhedral combinatorics, integer and linear programming, and computational geometry.     

Short correctness proofs for two self-stabilizing algorithms under the distributed daemon model

The distributed daemon model introduced by Burns in 1987 is a natural generalization of the central daemon model introduced by Dijkstra in 1974. In this paper, we show that a well-known shortest path algorithm is self-stabilizing under the distributed daemon model. Although this result has been proven only recently, the correctness proof provided here is from a different point of view and is much more concise. We also show that Bruell et al.’s center-finding algorithm is actually self-stabilizing under the distributed daemon model. Finally, we compute the worst-case stabilization times of the two algorithms under the distributed daemon model.     

On the complexity of finding paths in a two‐dimensional domain I: Shortest paths

The computational complexity of finding a shortest path in a two‐dimensional domain is studied in the Turing machine‐based computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomial‐time computable two‐dimensional domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

New models for shortest path problem with fuzzy arc lengths

This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.     

Optimal ship navigation with safety distance and realistic turn constraints

We consider the optimal ship navigation problem wherein the goal is to find the shortest path between two given coordinates in the presence of obstacles subject to safety distance and turn-radius constraints. These obstacles can be debris, rock formations, small islands, ice blocks, other ships, or even an entire coastline. We present a graph-theoretic solution on an appropriately-weighted directed graph representation of the navigation area obtained via 8-adjacency integer lattice discretization and utilization of the A^∗ algorithm. We explicitly account for the following three conditions as part of the turn-radius constraints: (1) the ship’s left and right turn radii are different, (2) ship’s speed reduces while turning, and (3) the ship needs to navigate a certain minimum number of lattice edges along a straight line before making any turns. The last constraint ensures that the navigation area can be discretized at any desired resolution. Once the optimal (discrete) path is determined, we smoothen it to emulate the actual navigation of the ship. We illustrate our methodology on an ice navigation example involving a 100,000 DWT merchant ship and present a proof-of-concept by simulating the ship’s path in a full-mission ship handling simulator.     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

On Formality of a Class of Compact Homogeneous Spaces

We prove the formality property of any homogeneous space G/G generated by an automorphism of finite order of a compact simple Lie group G.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

区域高技术产业技术创新效率测度与提升路径研究——基于共享投入关联型两阶段DEA模型

将高技术产业创新过程划分为技术研发和经济转化两个阶段,考虑初始创新投入在两阶段分配、非研发投入及新产品开发费用等因素对创新产出的影响,构建共享投入关联型两阶段DEA模型,并测度了2013~2015创新年度中国大陆30个省份的高技术产业技术创新整体效率与两阶段效率。结果表明:大多数区域高技术产业初始创新投入对研发产出和经济产出均有影响;高技术产业技术创新整体效率与两阶段效率都较低,且各区域创新效率水平差异较大;技术研发效率水平高于整体效率水平,而经济转化效率水平低于整体效率水平。最后,依据高技术产业技术创新两阶段效率及其在整体效率中的权重对各区域进行重分类,有针对性地提出了单边突破式、双向协调式等多条技术创新效率提升路径。