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 obta...
详细信息
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].
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 outputsensitivealgorithm for Boolean matrix product and its witnesse...
详细信息
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 outputsensitivealgorithm 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.
作者:
Rada, MiroslavCerny, MichalUniv 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...
详细信息
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.
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. ...
详细信息
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.
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 v...
详细信息
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/).
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...
详细信息
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)-time algorithm to compute such a maximum independent set. (c) 2006 Wiley Periodicals, Inc.
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 Euclid...
详细信息
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.
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...
详细信息
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.
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 co...
详细信息
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.
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...
详细信息
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 outputsensitive 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 outputsensitive 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.
暂无评论