共查询到20条相似文献,搜索用时 15 毫秒
1.
Let
be some set of orientations, that is,
. We consider the consequences of defining visibility based on curves that are monotone with respect to the orientations in
. We call such curves
-staircases. Two points p andq in a polygonP are said to
-see each other if an
-staircase fromp toq exists that is completely contained inP. The
-kernel of a polygonP is then the set of all points which
-see all other points. The
-kernel of a simple polygon can be obtained as the intersection of all {}-kernels, with
. With the help of this observation we are able to develop an
algorithm to compute the
-kernel of a simple polygon, for finite
. We also show how to compute theexternal
-kernel of a polygon in optimal time
. The two algorithms are combined to compute the (
-kernel of a polygon with holes in time
.This work was supported by the Deutsche Forschungsgemeinschaft under Grant No. Ot 64/5-4 and the Natural Sciences and Engineering Research Council of Canada and Information Technology Research Centre of Ontario. 相似文献
2.
Mohammad A. Shokrollahi 《Computational Complexity》1991,1(2):157-181
In the present paper we shall show that the rank of the finite field
regarded as an
-algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of
-rational points of an algebraic curve of genus 2 over
. Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound
. For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound. 相似文献
3.
Yu. N. Sotskov 《Cybernetics and Systems Analysis》1990,26(5):686-692
We consider the time-optimal scheduling problemn/m/J
of n jobs with fixed routes on m machines. The problem3/m/J/
with identical routes and the problem3/5/J/
are shown to be NP-hard. Similar results are obtained for the problem of minimizing the mean processing time of three jobs on m machines.Translated from Kibernetika, No. 5, pp. 50–54, September–October, 1990. 相似文献
4.
Let
be a finite field withq elements and
a rational function over
. No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on
. The problem has been shown to be in co-R
co-NP, and in this paper we prove that it is inR
NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over
. Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented. 相似文献
5.
Seth Breidbart 《Theory of Computing Systems》1978,12(1):129-131
We show that for any alphabet there is a setL
* such that ifC is any infinite co-infinite context-free language over , thenL
splitsC (i.e., each ofL
C,L
,
C, and
is infinite).Preparation of this paper was supported in part by the National Science Foundation under Grant No. MCS77-11360. 相似文献
6.
Nader H. Bshouty Yishay Mansour Baruch Schieber Prasson Tiwari 《Computational Complexity》1992,2(3):244-255
Given an integerk, and anarbitrary integer greater than
, we prove a tight bound of
on the time required to compute
with operations {+, –, *, /, ·, }, and constants {0, 1}. In contrast, when the floor operation is not available this computation requires (k) time. Using the upper bound, we give an
time algorithm for computing log loga, for alln-bit integersa. This upper bound matches the lower bound for computing this function given by Mansour, Schieber, and Tiwari. To the best of our knowledge these are the first non-constant tight bounds for computations involving the floor operation. 相似文献
7.
Optimization of rotor blades for combined structural,dynamic, and aerodynamic properties 总被引:1,自引:1,他引:0
A helicopter is intrinsically interdisciplinary due to the close coupling among aerodynamics, dynamics, and the blade structural details. Therefore a design optimization with proper interactions among appropriate disciplines (such as structure, dynamics, and aerodynamics) can offer significant benefit to improve rotor performance. This paper studies the integration of structure, dynamics, and aerodynamics in design optimization of helicopter rotor blades. The optimization is performed to minimize the rotor power required and to satisfy design requirements from structure (minimum blade weight and safe stress margin and fatigue life) and dynamics (proper placement of blade natural frequencies and free of flutter). An effort is made to formulate an effective strategy for combining these various requirements in the optimization process. The paper also presents a way for an intelligent phasing of this interdisciplinary optimization to overcome the hurdles due to conflicting demands on the design variables which arise from different disciplines.Notation
nondimensional leading edge mass size, = a/R
-
C
T
rotor thrust coefficient
-
C
P
rotor power coefficient
-
nondimensional chord,
=c/R
-
nondimensional lumped mass size,
=d/R
-
F(x)
objective function
-
G
j
(x)
j-th inequality constraint function
-
H
j
(x)
j-th equality constraint function
-
R
blade radius, meters
-
nondimensional blade radial coordinate,
=r/R
-
nondimensional web thickness,
=s
1/R
-
nondimensional web thickness,
=s
2/R
-
t
nondimensional flange thickness,
=t/R
- x
vector of design variables
-
x
i
i-th component of vector of design variables
-
blade pitch angle 相似文献
8.
Any given n×n matrix A is shown to be a restriction, to the A-invariant subspace, of a nonnegative N×N matrix B of spectral radius (B) arbitrarily close to (A). A difference inclusion
, where
is a compact set of matrices, is asymptotically stable if and only if
can be extended to a set
of nonnegative matrices B with
or
. Similar results are derived for differential inclusions. 相似文献
9.
Franco Montagna 《Journal of Logic, Language and Information》2000,9(1):91-124
We investigate the variety corresponding to a logic (introduced in Esteva and Godo, 1998, and called there), which is the combination of ukasiewicz Logic and Product Logic, and in which Gödel Logic is interpretable. We present an alternative (and slightly simpler) axiomatization of such variety. We also investigate the variety, called the variety of
algebras, corresponding to the logic obtained from by the adding of a constant and of a defining axiom for one half. We also connect
algebras with structures, called f-semifields, arising from the theory of lattice-ordered rings, and prove that every
algebra
can be regarded as a structure whose domain is the interval [0, 1] of an f-semifield
, and whose operations are the truncations of the operations of
to [0, 1]. We prove that such a structure
is uniquely determined by
up to isomorphism, and we establish an equivalence between the category of
algebras and that of f-semifields. 相似文献
10.
M. Drmota 《Algorithmica》2001,29(1-2):89-119
By using analytic tools it is shown that the expected value of the heightH
n
of binary search trees of sizen is asymptotically given by EH
n
=c logn+
(log logn) and its variance by VH
n
=
((log logn)2), wherec=4.31107 …. The same bounds have been obtained by Devroye and Reed [3] by completely different methods.
Dedicated to Philippe Flajolet on the occasion of his 50th birthday
This research was supported by the Austrian Science Foundation FWF, Grant P10187-MAT.
Online publication September 22, 2000. 相似文献
11.
Lajos Rónyai 《Computational Complexity》1992,2(3):225-243
This paper addresses an algorithmic problem related to associative algebras. We show that the problem of deciding if the index of a given central simple algebra
over an algebraic number field isd, whered is a given natural number, belongs to the complexity classN P co N P. As consequences, we obtain that the problem of deciding if
is isomorphic to a full matrix algebra over the ground field and the problem of deciding if
is a skewfield both belong toN P co N P. These results answer two questions raised in [25]. The algorithms and proofs rely mostly on the theory of maximal orders over number fields, a noncommutative generalization of algebraic number theory. Our results include an extension to the noncommutative case of an algorithm given by Huang for computing the factorization of rational primes in number fields and of a method of Zassenhaus for testing local maximality of orders in number fields. 相似文献
12.
Define the MOD
m
-degree of a boolean functionF to be the smallest degree of any polynomialP, over the ring of integers modulom, such that for all 0–1 assignments
,
iff
. We obtain the unexpected result that the MOD
m
-degree of the OR ofN variables is
, wherer is the number of distinct prime factors ofm. This is optimal in the case of representation by symmetric polynomials. The MOD
n
function is 0 if the number of input ones is a multiple ofn and is one otherwise. We show that the MOD
m
-degree of both the MOD
n
and
functions isN
(1) exactly when there is a prime dividingn but notm. The MOD
m
-degree of the MOD
m
function is 1; we show that the MOD
m
-degree of
isN
(1) ifm is not a power of a prime,O(1) otherwise. A corollary is that there exists an oracle relative to which the MOD
m
P classes (such as P) have this structure: MOD
m
P is closed under complementation and union iffm is a prime power, and MOD
n
P is a subset of MOD
m
P iff all primes dividingn also dividem. 相似文献
13.
Thomas Kaijser 《Journal of Mathematical Imaging and Vision》1998,9(2):173-191
Computing the Kantorovich distance for images is equivalent to solving a very large transportation problem. The cost-function of this transportation problem depends on which distance-function one uses to measure distances between pixels.In this paper we present an algorithm, with a computational complexity of roughly order
(N2), where N is equal to the number of pixels in the two images, in case the underlying distance-function is the L1-metric, an approximation of the L2-metric or the square of the L2-metric; a standard algorithm would have a computational complexity of order
(N3). The algorithm is based on the classical primal-dual algorithm.The algorithm also gives rise to a transportation plan from one image to the other and we also show how this transportation plan can be used for interpolation and possibly also for compression and discrimination. 相似文献
14.
Terry Huntsberger 《Autonomous Robots》2001,11(3):341-346
Robotic missions beyond 2013 will likely be precursors to a manned habitat deployment on Mars. Such missions require robust control systems for long duration activities. Current single rover missions will evolve into deployment of multiple, heterogeneous cooperating robotic colonies. This paper describes the map-making memory and action selection mechanism of BISMARC (
iologically
nspired
ystem for
ap-based
utonomous
over
ontrol) that is currently under development at the Jet Propulsion Laboratory in Pasadena, CA (Huntsberger and Rose, Neutral Networks, 11(7/8):1497–1510). BISMARC is an integrated control system for long duration missions involving robots performing cooperative tasks. 相似文献
15.
We consider the modified conjugate gradient procedure for solving A
=
in which the approximation space is based upon the Krylov space associated with A
1/p
and
, for any integer p. For the square-root MCG (p=2) we establish a sharpened bound for the error at each iteration via Chebyshev polynomials in
. We discuss the implications of the quickly accumulating effect of an error in
in the initial stage, and find an error bound even in the presence of such accumulating errors. Although this accumulation of errors may limit the usefulness of this method when
is unknown, it may still be successfully applied to a variety of small, almost-SPD problems, and can be used to jump-start the conjugate gradient method. Finally, we verify these theoretical results with numerical tests. 相似文献
16.
M. A. Shepilov 《Cybernetics and Systems Analysis》1987,23(2):233-238
Conclusion The obvious deficiency of the method (1.3), (1.9) is the possible difficulty of the operation
. In connection with this one can note that all the above given statements remain valid if the number
is replaced by some positive lower bound of |f(t
k
,x)| on
.In computational methods, the presence of the Lipschitz constant is considered as a deficiency. In connection with this we can note that the Lipschitz constant L can be replaced by any of its upper estimates. For example, for a differentiable function f(z) one can take
.Translated from Kibernetika, No. 2, pp. 71–74, March–April, 1987. 相似文献
17.
The paper describes an improved algorithm for computing cohomologies of Lie (super)algebras. The original algorithm developed earlier by the author of this paper is based on the decomposition of the entire cochain complex into minimal subcomplexes. The suggested improvement consists in the replacement of the arithmetic of rational or integer numbers by a more efficient arithmetic of modular fields and the use of the relationship dim H
k(
p) dimH
k() between the dimensions of cohomologies over an arbitrary modular field
p = /p and the filed of rational numbers . This inequality allows us to rapidly find subcomplexes for which dimH
k(
p) > 0 (the number of such subcomplexes is usually not great) using computations over an arbitrary
p and, then, carry out all required computations over in these subcomplexes. 相似文献
18.
Algorithms and optimality of scheduling soft aperiodic requests in fixed-priority preemptive systems
In this paper, we investigate the problem of scheduling soft aperiodic requests in systems where periodic tasks are scheduled on a fixed-priority, preemptive basis. First, we show that given any queueing discipline for the aperiodic requests, no scheduling algorithm can minimize the response time of every aperiodic request and guarantee that the deadlines of the periodic tasks are met when the periodic tasks are scheduled on a fixed-priority, preemptive basis. We then develop two algorithms: Algorithm
is locally optimal in that it minimizes the response time of the aperiodic request at the head of the aperiodic service queue. Algorithm
is globally optimal in that it completes the current backlog of work in the aperiodic service queue as early as possible. 相似文献
19.
We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule
, where
is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials
, we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For
and
, the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.
相似文献
20.
J. E. Hopcroft 《Theory of Computing Systems》1969,3(2):119-124
LetG andG
0 be context-free grammars. Necessary and sufficient conditions onG
0 are obtained for the decidability ofL(G
0)
L((G) It is also shown that it is undecidable for whichG
0,L(G)
is decidable. Furthermore, given thatL(G)
is decidable for a fixedG
0, there is no effective procedure to determine the algorithm which decidesL(G)
IfL(G
0) is a regular set,L(G) = L(G
0) is decidable if and only ifL(G
0) is bounded. However, there exist non-regular, unboundedL(G
0) for whichL(G) = L(G
0) is decidable. 相似文献