检索结果-内蒙古大学图书馆

output-sensitive algorithm for computing β-skeletons

COMPUTING 2000年第3期65卷 285-289页

作者： Mukhopadhyay, A Rao, SV Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada Indian Inst Technol Dept Comp Sci & Engn Guwahati 781001 Assam India

The beta -skeleton is a measure of the internal shape of a planar set of points. We get an entire spectrum of shapes by varying the parameter beta. For a fixed value of beta, a beta -skeleton is a geometric graph obtained by joining each pair of points whose beta -neighborhood is empty. For beta greater than or equal to 1, this neighborhood of a pair of points p(i),p(j) is the interior of the intersection of two circles of radius beta\(p(i)p(j)) over bar\/2, centered at the points (1 - beta /2)p(i) + (beta /2)p(j) and (beta /2)p(i) + (1 - beta /2)p(j), respectively. For beta epsilon (0, 1], it is the interior of the intersection of two circles of radius \(p(i)p(j)) over bar\(2 beta), passing through p(i) and p(j). In this paper we present an output-sensitive algorithm for computing a beta -skeleton in the metrics II and l(infinity) for any beta greater than or equal to 2. This algorithm is in O(n log n + k), where k is size of the output graph. The complexity of the previous best known algorithm is in O(n(5/2) log n) [7].

关键词： computational geometry beta-skeleton shape of a point set output-sensitive algorithm

来源：评论

学校读者我要写书评

暂无评论

A Fast output-sensitive algorithm for Boolean Matrix Multiplication

引用

algorithmICA 2011年第1期61卷 36-50页

作者： Lingas, Andrzej Lund Univ Dept Comp Sci S-22100 Lund Sweden

We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast outputsensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time (O) over tilde (n(2)s(omega/2-1)), where the input matrices have size nxn, the number of non-zero entries in the product matrix is at most s, omega is the exponent of the fast matrix multiplication and (O) over tilde (f(n)) denotes O(f(n)log(d) n) for some constant d. By the currently best bound on., its running time can be also expressed as (O) over tilde (n(2)s(0.188)). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n(1.232) and it is never slower than the fast (O) over tilde (n(omega))-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form (O) over tilde (n(omega(1/2) (logns, 1,1))), where omega(p, q, t) is the exponent of the fast multiplication of an n(p) x n(q) matrix by an n(q) x n(t) matrix. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms.

关键词： Boolean matrix multiplication Rectangular matrix multiplication output-sensitive algorithm Time complexity

来源：评论

学校读者我要写书评

暂无评论

A NEW algorithm FOR ENUMERATION OF CELLS OF HYPERPLANE ARRANGEMENTS AND A COMPARISON WITH AVIS AND FUKUDA'S REVERSE SEARCH

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第1期32卷 455-473页

作者： Rada, Miroslav Cerny, Michal Univ Econ Fac Finance & Accounting Nam W Churchilla 4 Prague 13067 3 Czech Republic Univ Econ Fac Informat & Stat Nam W Churchilla 4 Prague 13067 3 Czech Republic

We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of hyperplane arrangements (or dually, for the enumeration of vertices of generator-presented zonotopes). The algorithm is based on an incremental construction of the graph of cells of the arrangement. IncEnu is compared to Avis and Fukuda's Reverse Search (RS), including its later improvements by Sleumer and others. The basic versions of IncEnu and RS are not directly comparable, since they solve different numbers of linear programs (LPs) of different sizes. We therefore reformulate our algorithm as a version that permits comparison with RS in terms of the number of LPs solved. The result is that both IncEnu and RS have "the same" complexity-theoretic properties (compactness, output-polynomiality, worst-case bounds, tightness of bounds). In spite of the fact that IncEnu and RS have the same asymptotic bounds, it is proved that IncEnu is faster than RS by a nontrivial additive term. Our computational experiments show that for most test cases IncEnu is significantly faster than RS in practice. Based on the results obtained, we conjecture that IncEnu is O(d) times faster for nondegenerate arrangements, where d denotes the dimension of the arrangement.

关键词： arrangements cell enumeration zonotopes output-sensitive algorithm compact algorithm

来源：评论

学校读者我要写书评

暂无评论

Computing homotopic shortest paths in the plane

引用

JOURNAL OF algorithmS 2003年第2期49卷 284-303页

作者： Bespamyatnikh, S Univ Texas Dept Comp Sci Richardson TX 75083 USA

We address the problem of computing homotopic shortest paths in the presence of obstacles in the plane. Problems on homotopy of paths received attention very recently [Cabello et al., in: Proc. 18th Annu. ACM Sympos. Comput. Geom., 2002, pp. 160-169;Efrat et al., in: Proc. 10th Annu. European Sympos. algorithms, 2002, pp. 411-423]. We present two output-sensitive algorithms, for simple paths and non-simple paths. The algorithm for simple paths improves the previous algorithm [Efrat et al., in: Proc. 10th Annu. European Sympos. algorithms, 2002, pp. 411-423]. The algorithm for non-simple paths achieves O (log(2) n) time per output vertex which is an improvement by a factor of O (n/log(2)n) of the previous algorithm [Hershberger, Snoeyink, Comput. Geom. Theory Appl. 4 (1994) 63-981, where n is the number of obstacles. The running time has an overhead O (n(2+epsilon)) for any positive constant e. In the case k < n2+e, where k is the total size of the input and output, we improve the running to O((n + k + (nk)(2/3)) log(O(1)) n). (C) 2003 Elsevier Inc. All rights reserved.

关键词： shortest path homotopy output-sensitive algorithm

来源：评论

学校读者我要写书评

暂无评论

Constant amortized time enumeration of Eulerian trails

引用

THEORETICAL COMPUTER SCIENCE 2022年 923卷 1-12页

作者： Kurita, Kazuhiro Wasa, Kunihiro Natl Inst Informat Tokyo Japan Toyohashi Univ Technol Toyohashi Aichi Japan Hosei Univ Tokyo Japan

In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinctif the edge sequences are not identical, and they are said to be vertex-distinctif the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O(N+ m) total time, where Nis the number of solutions and mis the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015]. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Eulerian trail Enumeration algorithm output-sensitive algorithm Constant amortized time

来源：评论

学校读者我要写书评

暂无评论

Maximum independent set for intervals by divide and conquer with pruning

引用

NETWORKS 2007年第2期49卷 158-159页

作者： Snoeyink, Jack Univ N Carolina Dept Comp Sci Chapel Hill NC 27599 USA

Suppose a given set of n intervals contains a maximum independent set of k disjoint intervals. This brief note demonstrates that "divide and conquer with pruning" produces an easy, output-sensitive O(n log k... 详细信息

关键词： interval graph maximum independent set output-sensitive algorithm divide and conquer

来源：评论

学校读者我要写书评

暂无评论

Skew Voronoi diagrams

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1999年第3期9卷 235-247页

作者： Aichholzer, O Aurenhammer, F Chen, DZ Lee, DT Papadopoulou, E Graz Univ Technol Inst Theoret Comp Sci A-8010 Graz Austria IBM Corp Thomas J Watson Res Ctr Yorktown Heights NY 10598 USA

On a tilted plane T in three-space, skew distances are defined as the Euclidean distance plus a multiple of the signed difference in height. Skew distances may model realistic environments more closely than the Euclidean distance. Voronoi diagrams and related problems under this kind of distances are investigated. A relationship to convex distance functions and to Euclidean Voronoi diagrams for planar circles is shown, and is exploited for a geometric analysis and a plane-sweep construction of Voronoi diagrams on T. An output-sensitive algorithm running in time O(n log h) is developed, where n and h are the numbers of sites and non-empty Voronoi regions, respectively. The all nearest neighbors problem for skew distances, which has certain features different from its Euclidean counterpart, is solved in O(n log n) time.

关键词： direction-dependent distance Voronoi diagram additive weights output-sensitive algorithm

来源：评论

学校读者我要写书评

暂无评论

A Fast Shortest Path algorithm on Terrain-like Graphs

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2021年第2期66卷 737-750页

作者： Froese, Vincent Renken, Malte TU Berlin Fac 4 Algorithm & Computat Complex Berlin Germany

Terrain visibility graphs are a well-known graph class in computational geometry. They are closely related to polygon visibility graphs, but a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted considerable attention in the context of time series analysis (there called time series visibility graphs) with various practical applications in areas such as physics, geography, and medical sciences. Computing shortest paths in visibility graphs is a common task, for example, in line-of-sight communication. For time series analysis, graph characteristics involving shortest paths lengths (such as centrality measures) have proven useful. In this paper, we devise a fast output-sensitive shortest path algorithm on a superclass of terrain visibility graphs called terrain-like graphs (including all induced subgraphs of terrain visibility graphs). Our algorithm runs in O(d * log Delta) time, where d* is the length (that is, the number of edges) of the shortest path and Delta is the maximum vertex degree. Alternatively, with an O(n(2))-time preprocessing our algorithm runs in O(d*) time.

关键词： output-sensitive algorithm Polygon visibility graphs Time series visibility graphs Vertex ordering

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Subgraph Listing

引用

algorithmS 2014年第2期7卷 243-252页

作者： Zechner, Niklas Lingas, Andrzej Umea Univ Dept Comp Sci S-90187 Umea Sweden Lund Univ Dept Comp Sci S-22100 Lund Sweden

Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to Gasieniec et al. for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.

关键词： subgraph subgraph isomorphism subgraph listing clique triangle output-sensitive algorithm time complexity

来源：评论

学校读者我要写书评

暂无评论

ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2013年第6期23卷 443-459页

作者： Papadopoulou, Evanthia Dey, Sandeep Kumar Univ Svizzera Italiana Fac Informat Lugano Switzerland

The farthest line-segment Voronoi diagram illustrates properties surprisingly different from its counterpart for points: Voronoi regions may be disconnected and they are not characterized by convex-hull properties. In this paper we introduce the farthest hull and its Gaussian map as a closed polygonal curve that characterizes the regions of the farthest line-segment Voronoi diagram, and derive tighter bounds on the (linear) size of this diagram. With the purpose of unifying construction algorithms for farthest-point and farthest line-segment Voronoi diagrams, we adapt standard techniques to construct a convex hull and compute the farthest hull in O(n log n) or output sensitive O(n log h) time, where n is the number of line-segments and his the number of faces in the corresponding farthest Voronoi diagram. As a result, the farthest line-segment Voronoi diagram can be constructed in output sensitive O(n log h) time. Our algorithms are given in the Euclidean plane but they hold also in the general L-p metric, 1 <= p <= infinity.

关键词： Voronoi diagram farthest site line segment Gaussian map farthest hull output-sensitive algorithm L-p metric

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：