共查询到20条相似文献,搜索用时 15 毫秒
1.
We consider a restricted version of the art gallery problem within simple polygons in which the guards are required to lie
on a given one-dimensional object, a watchman route. We call this problem the vision
point
problem . We prove the following:
• The original art gallery problem is NP-hard for the very restricted class of street polygons.
• The vision point problem can be solved efficiently for the class of street polygons.
• A linear time algorithm for the vision point problem exists for the subclass of street polygons called straight
walkable polygons.
Received June 6, 1996; revised September 12, 1997. 相似文献
2.
确定两个任意简单多边形空间关系的算法 总被引:4,自引:0,他引:4
阐述了把简单多边形的边分为奇偶边的新思想,根据一多边形的边与另一多边形的拓朴关系,划分边为5种拓朴类型:内边、外边、重叠边、相交边、复杂边,进而给出了确定两个多边形空间关系的算法,算法的时间复杂度为O((n+m)log(n+m)),其中n、m分别是两输入多边形的顶点数。该算法建立在数学理论基础之上,没有奇异情况需要处理,易于编程实现。算法的主要思想对确定两个简单多面体空间关系亦有参考价值。 相似文献
3.
A Linear-Time Approximation Scheme for Minimum Weight Triangulation of Convex Polygons 总被引:1,自引:0,他引:1
A linear-time heuristic for minimum weight triangulation of convex polygons is presented. This heuristic produces a triangulation
of length within a factor 1 + ε from the optimum, where ε is an arbitrarily small positive constant. This is the first subcubic algorithm that guarantees such an approximation factor,
and it has interesting applications.
Received November 21, 1996; revised March 9, 1997. 相似文献
4.
This paper deals with questions from convex geometry related to shape matching. In particular, we consider the problem of
moving one convex figure over another, minimizing the area of their symmetric difference. We show that if we just let the
two centers of gravity coincide, the resulting symmetric difference is within a factor of 11/3 of the optimum. This leads to efficient approximate matching algorithms for convex figures.
Received November 1996; revised March 1997. 相似文献
5.
Given a set P of polygons in three-dimensional space, two points p and q are said to be visible from each other with respect to P if the line segment joining them does not intersect any polygon in P . A point p is said to be completely visible from an area source S if p is visible from every point in S . The completely visible region
CV(S, P) from S with respect to P is defined as the set of all points in three-dimensional space that are completely visible from S .
We present two algorithms for computing CV(S, P) for P with a total of n vertices and a convex polygonal source S with m vertices. Our first result is a divide-and-conquer algorithm which runs in O(m
2
n
2
α(mn)) time and space, where α(mn) is the inverse of Ackermann's function. We next give an incremental algorithm for computing CV(S,P) in O(m
2
n+mn
2
α(n)) time and O(mn+n
2
) space. We also prove that CV(S,P) consists of Θ(mn+n
2
) surface elements such as vertices, edges, and faces.
Received November 16, 1995; revised November 11, 1996. 相似文献
6.
一种剖分平面多边形的通用算法描述 总被引:1,自引:1,他引:1
提出了一种用梯形来剖分非单调平面多边形的通用算法,算法包括三部分:初始化,梯形化和优化(后处理),所处理的多边形可以包含孔,孔可以嵌套。本算法的时间复杂度是O(n^2log2n). 相似文献
7.
对一种用梯形来剖分非单调平面多边形的通用算法,在AMD雷鸟750MHZ CPU计算机上进行了计算,结果表明,本算法可以有效、经济地处理大量复杂的多边形,经优化处理后,可减少约34%的梯形个数。 相似文献
8.
A polyhedron P is castable if its boundary can be partitioned by a plane into two polyhedral terrains. Castable polyhedra can be manufactured
easily using two cast parts, where each cast part can be removed from the object without breaking the cast part or the object.
If we assume that the cast parts are each removed by a single translation, it is shown that for a simple polyhedron with n vertices, castability can be decided in time and linear space using a simple algorithm. A more complicated algorithm solves the problem in time and space, for any fixed ε > 0. In the case where the cast parts are to be removed in opposite directions, a simple O(n
2
)-time algorithm is presented. Finally, if the object is a convex polyhedron and the cast parts are to be removed in opposite
directions, a simple algorithm is presented.
Received June 1, 1994; revised May 25, 1995. 相似文献
9.
10.
设P和Q为平面内两个互不相交的简单多边形,若P在平面内绕某点旋转,文中讨论了其旋转可移动性问题,通过提取多边形的单调链,采用曲线扫描法,给出了求其最大可旋转角度及碰撞部位的算法,与现有的算法相比,降低了时间复杂性。 相似文献
11.
V. J. Milenkovic 《Algorithmica》2000,27(1):57-86
Exact implementations of algorithms of computational geometry are subject to exponential growth in running time and space.
In particular, coordinate bit-complexity can grow exponentially when algorithms are cascaded : the output of one algorithm becomes the input to the next. Cascading is a significant problem in practice. We propose a
geometric rounding technique: shortest path rounding . Shortest path rounding trades accuracy for space and time and eliminates the exponential cost introduced by cascading.
It can be applied to all algorithms which operate on planar polygonal regions, for example, set operations, transformations,
convex hull, triangulation, and Minkowski sum. Unlike other geometric rounding techniques, shortest path rounding can round
vertices to arbitrary lattices, even in polar coordinates, as long as the rounding cells are connected. (Other rounding techniques
can only round to the integer grid.) On the integer grid, shortest path rounding introduces less combinatorial change and
geometric error than the other rounding methods. Three algorithms are given for shortest path rounding, one of which we have
used in industrial application software since 1992. In combination with recent advances in exact floating point evaluation
of numerical primitives, shortest path geometric rounding yields a practical solution to numerical issues in computational
geometry. Geometric algorithms can be implemented exactly on floating point input coordinates; the exact output coordinates
can be rounded to accurate floating point approximations; and the cost of each arithmetic operation is only a little more
than if it were implemented as a single hardware floating point operation.
Received February 7, 1997; revised September 9, 1998. 相似文献
12.
We present a randomized algorithm for computing the Voronoi diagram of line segments using coarse-grained parallel machines.
Operating on P processors, for any input of n line segments, this algorithm performs O((n log n)/P) local operations per processor, O(n/P) messages per processor, and O(1) communication phases, with high probability for n=Ω(P
3+ε
) .
Received June 1, 1997; revised March 10, 1998. 相似文献
13.
14.
针对机器刺绣和平面型腔行切加工对图形分解的要求,定义了广义梯形的概念,提出了广义梯形分解平面多边形的算法.广义梯形结合了梯形的定义和单调链的思想,广义梯形分解算法以对顶点的分类为基础,借鉴文献(Lorenzetto G P,Datta A,Thomas R C.A fast trapezoidation technique for planar polygons.Computers & Graphics,2002,26(2):281~289)的快速梯形分解框架,通过扫描线方法将平面多边形分解为广义梯形.该算法能够分解内嵌多个环的复杂多边形,分析及测试表明,其时间复杂度为O(nlogn). 相似文献
15.
This paper presents a theoretical and experimental study on two different methods to evaluate the sign of a determinant with
integer entries. The first one is a method based on the Gram—Schmidt orthogonalization process which has been proposed by
Clarkson [Cl]. We review his algorithm and propose a variant of his method, for which we give a complete analysis. The second
method is an extension to n × n determinants of the ABDPY method [ABD+2] which works only for 2 × 2 and 3 × 3 determinants. Both methods compute the sign of an n× n determinant whose entries are integers on b bits, by using exact arithmetic on only b +O(n) bits. Furthermore, both methods are adaptive, dealing quickly with easy cases and resorting to full-length computation only
for null determinants.
Received December 30, 1996; revised September 16, 1998. 相似文献
16.
An area light source in three-dimensional space shines past a scene polygon to generate two types of shadow volumes for each
scene polygon, i.e., one with partial occlusion and the other with complete occlusion. These are called penumbra and umbra, respectively. In this paper we propose linear-time algorithms for computing the penumbra and the umbra of a scene polygon
from an area light source, respectively.
Received June 27, 1995; revised May 20, 1996. 相似文献
17.
Abstract. The traditional worst-case analysis often fails to predict the actual behavior of the running time of geometric algorithms
in practical situations. One reason is that worst-case scenarios are often very contrived and do not occur in practice. To
avoid this, models are needed that describe the properties that realistic inputs have, so that the analysis can take these
properties into account.
We try to bring some structure to this emerging research direction. In particular, we present the following results:
• We show the relations between various models that have been proposed in the literature.
• For several of these models, we give algorithms to compute the model parameter(s) for a given (planar) scene; these algorithms
can be used to verify whether a model is appropriate for typical scenes in some application area.
• As a case study, we give some experimental results on the appropriateness of some of the models for one particular type
of scene often encountered in geographic information systems, namely certain triangulated irregular networks. 相似文献
18.
Abstract. We present a new line sweep algorithm, HEAPSWEEP, for reporting bichromatic (``purple') intersections between a red and
a blue family of line segments. If the union of the segments in each family is connected as a point set, HEAPSWEEP reports
all k purple intersections in time O((n+k) α(n) log
3
n) , where n is the total number of input segments and α(n) is the nearly constant inverse Ackermann function. To achieve these bounds, the algorithm maintains only partial information
about the vertical ordering between curves of the same color, using a new data structure called a kinetic queue . In order to analyze the running time of HEAPSWEEP, we also show that a simple polygon containing a set of n line segments can be partitioned into monotone regions by a set of vertical threads cutting these segments O(n log n) times. 相似文献
19.
Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm
is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R
d
, this leads to an O(n log n + c
k
n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c
k
) , whose total edge length is O(c
k
) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R
d
. These algorithms construct (i) in O(n log n + k
2
n) time, a k -fault-tolerant spanner with O(k
2
n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges. 相似文献
20.
确定任意简单多边形平移时碰撞部位的扫描算法 总被引:8,自引:0,他引:8
设P和Q为平面内任意两个互不相交的简单多边形,若P沿方向d平移时与Q碰撞,采用平面扫描法,通过提取多边形的单调链,给出了求其碰撞部位的算法,最坏情况下,算法的时间复杂性为O(m+n)log(m+n),其中n和m分别为多边形P与Q的边数,与现有的算法相比,降低了时间复杂性。 相似文献