共查询到20条相似文献,搜索用时 15 毫秒
1.
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. 相似文献
2.
3.
AnO(¦E¦log2
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
2)-time andO(n
2)-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. 相似文献
4.
Joseph ORourke 《Pattern recognition》1982,15(3):189-192
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 L1 (for k = 2) metrics. 相似文献
5.
Herbert S. Wilf 《Information Processing Letters》1984,18(3):119-121
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. 相似文献
6.
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. 相似文献
7.
8.
9.
O(m^2)时间求解SAT问题的随机算法 总被引:2,自引:1,他引:2
传统的求解SAT问题的随机算法主要是对满足解进行搜索,在找不到满足解的情况下,则无法正确判断问题的可满足性。该文提出了两个时间复杂度为O(m^2)求解SAT问题的随机算法SatTestl和SatTest2,这里m为CNF公式中的子句数。这两个随机算法是通过对不满足解数的估计来判断SAT问题的可满足性,不同于传统的随机算法。其中第二个算法SatTest2在搜索满足解的同时又可以对不满足解数进行估计,是对传统随机算法的重要改进。试验结果表明,文中提出的算法对相变区域的难SAT实例有较好的求解能力。 相似文献
10.
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. 相似文献
11.
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(T2). In contrast to discontinuous control for continuous-time VSS, the discrete-time sliding mode control need not be of switching type 相似文献
12.
Given a simple polygon P of n vertices, the watchman route problem asks for a shortest (closed) route inside P such that each point in the interior of 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(n4logn) time, which is too complicated to be suitable in practice. 相似文献
13.
Stefan Porschen Bert Randerath Ewald Speckenmeyer 《Annals of Mathematics and Artificial Intelligence》2005,43(1):173-193
Let F = C
1 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(20.18674n
). Thereby we improve a result in [2,3] stating X3SAT O(20.2072n
) and a bound of O(20.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(20.16254n
).An extended abstract of this paper was presented at the Fifth International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2002). 相似文献
14.
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|. 相似文献
15.
16.
17.
18.
Ioannis Koutis 《Information Processing Letters》2006,100(1):8-13
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. 相似文献
19.
Paul M.B. Vitányi 《Information Processing Letters》1985,21(3):147-152
To simulate two pushdown stores, or one queue, on-line by a one-head tape unit requires Ω(n1.618) time. 相似文献
20.
Godfried T. Toussaint 《Pattern recognition letters》1986,4(6):449-451
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. 相似文献