共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
D. A. Youngs 《Combinatorica》1995,15(2):289-295
In 1966 T. Gallai asked whether every criticalk-chromatic graph possesses an orientation having just one directed path of lengthk–1. In this note we show that in general the answer is negative, but also that the answer is affirmative whenk5 and the graph has maximal degree at mostk. 相似文献
3.
We consider the problem of planning the motion of an arbitraryk-sided polygonal robotB, free to translate and rotate in a polygonal environmentV bounded byn edges. We present an algorithm that constructs a single component of the free configuration space ofB in timeO((kn)
2+ɛ), for any ɛ>0. This algorithm, combined with some standard techniques in motion planning, yields a solution to the underlying
motion-planning problem, within the same running time.
Work on this paper by Dan Halperin has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford
Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper
by Micha Sharir has been supported by NSF Grants CCR-91-22103 and CCR-93-11127, by a Max-Planck Research Award, and by grants
from the U.S.-Israeli Binational Science Foundation, the Israel Science Fund administered by the Israeli Academy of Sciences,
and the G.I.F., the German-Israeli Foundation for Scientific Research and Development. A preliminary and extended version
of the paper has appeared as: D. Halperin and M. Sharir, Near-quadratic bounds for the motion planning problem for a polygon
in a polygonal environment,Proc. 34th IEEE Symp. on Foundations of Computer Science, 1993, pp. 382–391. Part of the work on the paper was carried out while Dan Halperin was at Tel Aviv University. 相似文献
4.
Micha Sharir 《纯数学与应用数学通讯》1995,48(9):1173-1186
We survey recent developments in algorithmic motion planning in robotics. © 1996 John Wiley & Sons, Inc. 相似文献
6.
Let G be a graph, and let D be a directed graph. Write G → D to mean that, no matter how the edges of G are given orientations, a copy of D must appear as a subgraph of the resulting oriented graph. It is proved that among all G for which G → D, the minimum chromatic number is equal to the minimum k for which Kk → hom(D), where hom(D) is the set of homomorphs of D. Next, necessary and sufficient conditions are given for a directed graph to have a homomorphism into a given transitive tournament, directed path, or directed cycle. These results are then applied to various cases of the above theorem. In particular, the minimum chromatic number is evaluated whenever D is an oriented forest, and all D are characterized for which the minimum chromatic number is no more than three. 相似文献
7.
Dan Halperin 《Discrete and Computational Geometry》1994,11(1):1-33
We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n
2) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set
of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches
near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with
three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement
in each case that we study can be Θ(n
3) in the worst case, and our single-cell bounds are of the formO(n
2
α(n)), O(n
2
logn), orO(n
2
α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space,
where the bounds are Θ(n) and Θ(n
2), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell.
A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323. 相似文献
8.
Gui-Xian Tian 《Linear algebra and its applications》2011,435(9):2140-2149
Let D be a digraph of order n and λ1,λ2,…,λn denote all the eigenvalues of the skew-adjacency matrix of D. The skew energy ES(D) of D is defined as . In this paper, it is proved that for any positive integer k≥3, there exists a k-regular graph of order n having an orientation D with . This work positively answers a problem proposed by Adiga et al. [C. Adiga, R. Balakrishnan, Wasin So, The skew energy of a digraph, Linear Algebra Appl. 432 (2010) 1825-1835]. In addition, a digraph is also constructed such that its skew energy is the same as the energy of its underlying graph. 相似文献
9.
We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and extending (and also simplifying) a previous NP-hardness result of Wilfong. The family considered includes a motion planning problem which forms the basis of a popular computer game called SOKOBAN. The decision problem corresponding to SOKOBAN is shown to be NP-hard. The motion planning problems considered are related to the “warehouseman's problem” considered by Hopcroft, Schwartz and Sharir, and to geometric versions of the motion planning problem on graphs considered by Papadimitriou, Raghavan, Sudan and Tamaki. 相似文献
10.
It is well known that every Eulerian orientation of an Eulerian -edge connected (undirected) graph is strongly -edge connected. A long-standing goal in the area is to obtain analogous results for other types of connectivity, such as node connectivity. We show that every Eulerian orientation of the hypercube of degree is strongly -node connected. 相似文献
11.
Robert-Paul Berretty Mark H. Overmars A. Frank van der Stappen 《Computational Geometry》1998,11(3-4):157-173
A fundamental task for an autonomous robot is to plan its own motions. Exact approaches to the solution of this motion planning problem suffer from high worst-case running times. The weak and realistic low obstacle density (L.O.D.) assumption results in linear complexity in the number of obstacles of the free space (Van der Stappen et al., 1997). In this paper we address the dynamic version of the motion planning problem in which a robot moves among polygonal obstacles which move along polylines. The obstacles are assumed to move along constant complexity polylines, and to respect the low density property at any given time. We will show that in this situation a cell decomposition of the free space of size O(n2(n) log2 n) can be computed in O(n2(n) log2 n) time. The dynamic motion planning problem is then solved in O(n2(n) log3 n) time. We also show that these results are close to optimal. 相似文献
12.
J. -P. Gauthier V. M. Zakalyukin 《Proceedings of the Steklov Institute of Mathematics》2007,256(1):62-79
This is the concluding work of our series devoted to the evaluation of the complexity and entropy of a motion planning problem
for a sub-Riemannian distribution. We consider some new cases of the dimension and codimension of the distribution, in particular,
(2, 3), (3, 4), and some other that are one-step-bracket-generating. We summarize all known estimations for low-dimensional
generic systems. They include all generic systems of corank less than 4 and other cases up to corank 10.
Published in Russian in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2007, Vol. 256, pp. 70–88. 相似文献
13.
G. Louchard 《BIT Numerical Mathematics》1986,26(1):17-34
The Brownian motion is shown to be a useful tool in analysing some sorting and tree manipulation algorithms. 相似文献
14.
Volker Schulz Richard Longman Hans Georg Bock 《Mathematical Methods in the Applied Sciences》1998,21(8):733-755
In space-based robotics, one of the most important problems is the disturbance to the satellite attitude and to the satellite microgravity environment caused by satellite mounted robot operation. This paper reports on computer-aided motion planning strategies to overcome this problem. Point-to-point motion designs are generated which not only connect prescribed start and end points of the robot motion, but also simultaneously return the satellite to its original attitude. Theoretical characterizations of some of those motion designs are presented, as well as numerical results. The computation time required to produce such motion designs is 1 or 2 min on a workstation. Thus, it can be practical to use these motion plans in space. © 1998 B. G. Teubner Stuttgart–John Wiley & Sons Ltd. 相似文献
15.
Planning time-optimal motions has been a major focus of research in robotics. In this paper we consider the following problem:
given an object in two-dimensional physical space, an initial point, and a final point, plan a time-optimal obstacle-avoiding
motion for this object subject to bounds on the velocity and acceleration of the object. We give the first algorithm which
solves the problem exactly in the case where the velocity and acceleration bounds are given in theL
∞ norm. We further prove the following important results: a tracking lemma and a loop-elimination theorem, both of which are
applicable to the case of arbitrary norms. The latter result implies that, with or without obstacles, a path which intersects
itself can be replaced by one which does not do so and which takes time less than or equal to that taken by the original path.
The work of J. Canny and A. Rege was supported by NSF Grants IRI-89-58577 and IRI-90-14490 and by a David and Lucile Packard
Fellowship. J. Reif's work was supported in part by DARPA/ARO Contract DAAL03-88-K-0185, Air Force Contract AFSOR-87-0386,
ONR Contract N00014-K-0310, and DARPA/ISTO Contract N00014-88-K-0458. 相似文献
16.
The paper deals with the dynamics of a spherical rolling robot actuated by internal rotors that are placed on orthogonal axes. The driving principle for such a robot exploits nonholonomic constraints to propel the rolling carrier. A full mathematical model as well as its reduced version are derived, and the inverse dynamics are addressed. It is shown that if the rotors are mounted on three orthogonal axes, any feasible kinematic trajectory of the rolling robot is dynamically realizable. For the case of only two rotors the conditions of controllability and dynamic realizability are established. It is shown that in moving the robot by tracing straight lines and circles in the contact plane the dynamically realizable trajectories are not represented by the circles on the sphere, which is a feature of the kinematic model of pure rolling. The implication of this fact to motion planning is explored under a case study. It is shown there that in maneuvering the robot by tracing circles on the sphere the dynamically realizable trajectories are essentially different from those resulted from kinematic models. The dynamic motion planning problem is then formulated in the optimal control settings, and properties of the optimal trajectories are illustrated under simulation. 相似文献
17.
Chenbo Zhu J. Q. Hu Fengchun Wang Yifan Xu Rongzeng Cao 《Annals of Operations Research》2012,192(1):67-86
Increasingly, tourists are planning trips by themselves using the vast amount of information available on the Web. However,
they still expect and want trip plan advisory services. In this paper, we study the tour planning problem in which our goal
is to design a tour trip with the most desirable sites, subject to various budget and time constraints. We first establish
a framework for this problem, and then formulate it as a mixed integer linear programming problem. However, except when the
size of the problem is small, say, with less than 20–30 sites, it is computationally infeasible to solve the mixed-integer
linear programming problem. Therefore, we propose a heuristic method based on local search ideas. The method is efficient
and provides good approximation solutions. Numerical results are provided to validate the method. We also apply our method
to the team orienteering problem, a special case of the tour planning problem which has been considered in the literature,
and compare our method with other existing methods. Our numerical results show that our method produces very good approximation
solutions with relatively small computational efforts comparing with other existing methods. 相似文献
18.
19.
Hian Poh Yap 《Journal of Graph Theory》1980,4(3):309-314
Gol'dberg has recently constructed an infinite family of 3-critical graphs of even order. We now prove that if there exists a p(≥4)-critical graph K of odd order such that K has a vertex u of valency 2 and another vertex v ≠ u of valency ≤(p + 2)/2, then there exists a p-critical graph of even order. 相似文献