Characterizing and recognizing the visibility graph of a funnel-shaped polygon

A funnel, which is notable for its fundamental role in visibility algorithms, is defined as a polygon that has exactly three convex vertices, two of which are connected by a boundary edge. In this paper we investigate the visibility graph of a funnel which we call an F-graph.We first present two characterizations of an F-graph, one of whose sufficiency proof itself is a linear time Real RAM algorithm for drawing a funnel on the plane that corresponds to an F-graph. We next give a linear-time algorithm for recognizing an F-graph. When the algorithm recognizes an F-graph, it also reports one of the Hamiltonian cycles defining the boundary of its corresponding funnel. This recognition algorithm takes linear time even on a RAM.We finally show that an F-graph is weakly triangulated and therefore perfect, which agrees with the fact that perfect graphs are related to geometric structures.This work was supported in part by the Korea Science and Engineering Foundation under Grant 91-01-01.     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

Computing the relative neighborhood graph in the L1 and L∞ metrics

The Relative Neighborhood Graph (RNG) of a set of nk-dimensional points connects “relatively close” neighbors: two points are connected by an edge if they are at least as close to each other as to any other point. Toussaint recently investigated the properties of the RNG in the Euclidean metric and proposed algorithms for its computation. This note examines one of the open problems listed by Toussaint: the extension of the analysis to non-Euclidean metrics. It is shown that Bentley's range query data structures may be used to improve the speed of the best known RNG algorithm in the L_∞ (for k ? 2) and L₁ (for k = 2) metrics.     

Backtrack: An O(1) expected time algorithm for the graph coloring problem

Fix a number K, of colors. We consider the usual backtrack algorithm for the decision problem of K-colorability of a graph G. We show that the algorithm operates in average time that is O(1), as the number of vertices of G approaches infinity. For instance, a backtrack search tree for 3-coloring a graph has an average of about 197 nodes, averaged over all graphs of all sizes.     

Epileptic seizure detection in EEGs signals using a fast weighted horizontal visibility algorithm

This paper proposes a fast weighted horizontal visibility graph constructing algorithm (FWHVA) to identify seizure from EEG signals. The performance of the FWHVA is evaluated by comparing with Fast Fourier Transform (FFT) and sample entropy (SampEn) method. Two noise-robustness graph features based on the FWHVA, mean degree and mean strength, are investigated using two chaos signals and five groups of EEG signals. Experimental results show that feature extraction using the FWHVA is faster than that of SampEn and FFT. And mean strength feature associated with ictal EEG is significant higher than that of healthy and inter-ictal EEGs. In addition, an 100% classification accuracy for identifying seizure from healthy shows that the features based on the FWHVA are more promising than the frequency features based on FFT and entropy indices based on SampEn for time series classification.     

公交出行最优路径搜索的有向赋权图模型

当前的公交查询系统和模型在处理多目标和多模式查询时,存在着描述困难和缺乏灵活性的问题。为此,基于有向赋权图提出了一种新的公交出行最优路径搜索模型。该模型不仅可以让用户设定可接受的最大步行距离,而且通过灵活的赋权策略利用最短路径搜索算法可以满足个性化的查询要求,尤其是在多目标查询方面具有较强的表达能力。以真实的公交数据实验表明提出的模型有效、实用。     

用O(tlogt)的连接图求有障碍时的最短路径

针对有障碍时求两点间的最短路径这一问题,提出了极区和自由区的概念,并由此构造出一种新的强连接图ＣＦ,它由自由区的特征边和障碍的极边构成,其顶点数为Ｏ（ｔ）,边数为Ｏ（ｔｌｏｇｔ）,其中ｔ为障碍的极边数,而现有最佳连通图的顶点数和边数为Ｏ（ｔ＾２）,同时提出了时间复杂度为Ｏ（ｔｌｏｇ＾２ｔ）的高效ＧＦ构造算法,并使用“不改向”的启发式Ａ算法在ＧＦ中寻找两点间的最短路径。     

O（m^2）时间求解SAT问题的随机算法

传统的求解SAT问题的随机算法主要是对满足解进行搜索,在找不到满足解的情况下,则无法正确判断问题的可满足性。该文提出了两个时间复杂度为O（m^2）求解SAT问题的随机算法SatTestl和SatTest2,这里m为CNF公式中的子句数。这两个随机算法是通过对不满足解数的估计来判断SAT问题的可满足性,不同于传统的随机算法。其中第二个算法SatTest2在搜索满足解的同时又可以对不满足解数进行估计,是对传统随机算法的重要改进。试验结果表明,文中提出的算法对相变区域的难SAT实例有较好的求解能力。     

O(log logn)-time integer geometry on the CRCW PRAM

We study problems in computational geometry on PRAMs under the assumption that input objects are specified by points withO(logn)-bit coordinates, or, equivalently, with polynomially bounded integer coordinates. We show that in this setting many geometric problems can be solved in time O(log logn). The following five specific problems are investigated:closest pair of points, intersection of convex polygons, intersection of manhattan line segments, dominating set, andlargest empty square. Algorithms solving them are developed which operate in time O(log logn) on the arbitrary CRCW PRAM. The number of processors used is eitherO(n) orO(n logn).This research was supported in part by Grants KBN 2-2044-92-03, KBN 2-2043-92-03, and KBN 2-1190-91-01.     

An O(T2) boundary layer in sliding mode for sampled-datasystems

The use of a discontinuous control law (typically, sign functions) in a sampled-data system will bring about chattering phenomenon in the vicinity of the sliding manifold, leading to a boundary layer with thickness O(T), where T is the sampling period. However, by proper consideration of the sampling phenomenon in the discrete-time sliding mode control design, the thickness of the boundary layer can be reduced to O(T²). In contrast to discontinuous control for continuous-time VSS, the discrete-time sliding mode control need not be of switching type     

A linear-time 2-approximation algorithm for the watchman route problem for simple polygons

Given a simple polygon P$P$ of n$n$ vertices, the watchman route problem   asks for a shortest (closed) route inside P$P$ such that each point in the interior of P$P$ can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most two times that of the shortest watchman route. The best known algorithm for computing a shortest watchman route takes O(n⁴logn)$O(n^{4}logn)$ time, which is too complicated to be suitable in practice.     

Exact 3-satisfiability is decidable in time O(20.16254n)

Let F = C ₁ C _m be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C _i contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(2^0.18674n ). Thereby we improve a result in [2,3] stating X3SAT O(2^0.2072n ) and a bound of O(2^0.200002n ) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SAT O(2^0.16254n ).An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002).     

An O(k~2n~2) Algorithm to Find a k-Partition in a k-Connected Graph

Although there are polynomial algorithms of finding a 2-partition or a 3-partition for a simple undirected 2-connected or 3-connected graph respectively,there is no general algorithm of finding a k-partition for a k-connected graph G=(V,E),where k is the vertex connectivity of G.In this paper,an O(k^2n^2) general algorithm of finding a k-partition for a k-connected graph is proposed,where n=|V|.     

Parameterized complexity and improved inapproximability for computing the largest j-simplex in a V-polytope

We consider the problem of computing the squared volume of the largest j-simplex contained in an n-dimensional polytope presented by its vertices (a V-polytope). We show that the related decision problem is W[1]-complete, with respect to the parameter j. We also improve the constant inapproximability factor given in [A. Packer, Polynomial-time approximation of largest simplices in V-polytopes, Discrete Appl. Math. 134 (1-3) (2004) 213-237], by showing that there are constants μ<1,c>1 such that it is NP-hard to approximate within a factor of cμn the volume of the largest ⌊μn⌋-simplex contained in an n-dimensional polytope with O(n) vertices.     

An n1.618 lower bound on the time to simulate one queue or two pushdown stores by one tape

To simulate two pushdown stores, or one queue, on-line by a one-head tape unit requires Ω(n^1.618) time.     

A linear-time algorithm for solving the strong hidden-line problem in a simple polygon

A linear-time algorithm is presented for solving the strong hidden-line problem in a simple polygon P, or alternately, determining the region in P weakly visible from a specified edge of P. The algorithm combines results from visibility and shortest paths with the linear-time polygon triangulation algorithm discovered recently by Tarjan and Van Wyk. Previous published algorithms for the strong hidden-line problem require O(n logn) steps even after triangulation, where n is the cardinality of P.