Chao Chen, Michael Kerber · 2011
In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ> 0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the running time is O(C(1−δ)ΓR(n)log n), where C(1−δ)Γ is the number of homology classes with persistence at least (1−δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n×n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1−δ)Γn 2.376) algorithm, a O(C(1−δ)Γn 2.28) Las-Vegas algorithm, or a O(C(1−δ)Γn 2+ǫ) Monte-Carlo algorithm for an arbitrary ǫ> 0.
Cited by 0
Chao Chen, Michael Kerber · Computational Geometry · 2012
Cited by 36
Asish Mukhopadhyay, S. Venugopal Rao · Computing · 2000
Cited by 0
Hossein Ghasemalizadeh, Mohammadreza Razzazi · arXiv (Cornell University) · 2013
A set of points and a positive integer $m$ are given and our goal is to cover the maximum number of these point with $m$ disks. We devise the first output sensitive algorithm for this problem. We introduce a parameter $ρ$ as the maximum number of points that one disk can cover. In this paper first we solve the problem for $m=2$ in $O({nρ} + {ρ^3}\log ρ))$ time. The previous algorithm for this problem runs in $O({n^3}\log n)$ time. Our algorithm outperforms the previous algorithm because $ρ$ is much smaller than $n$ in many cases. Then we extend the algorithm for any value of $m$ and we solve the problem in $O(m{nρ} + {(mρ)^{2m - 1}}\log mρ)$ time. The previous algorithm for this problem runs in $O({n^{2m - 1}}\log n)$ time. Our algorithm runs faster than the previous algorithm because $mρ$ is smaller than $n$ in many cases. Our technique to obtain an output sensitive algorithm is to use a greedy algorithm to confine the areas that we should search to obtain the result. Our technique in this paper may be applicable in other set covering problems that deploy a greedy algorithm, to obtain faster solutions.
Cited by 0Open access
Laxmi Parida, Isidore Rigoutsos, Dan Platt · Lecture notes in computer science · 2001
Cited by 16
Chao Chen, Michael Kerber · 2011
In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε>0.
Cited by 16
Har-Peled, Sariel · ArXiv.org · 2026
$\def\DD{\bf δ}\def\CH{\mathop{\mathrm{ConvexHull}}}\newcommand{\LL}{\cal {L}} \newcommand{\ZZ}{\mathbb{Z}} $ Given a convex body $C$ in the plane, its discrete hull is $C^0 = \CH( C \cap \LL )$, where $\LL = \ZZ \times \ZZ$ is the integer lattice. We present an $O( |C^0| \log \DD(C) )$-time algorithm for calculating the discrete hull of $C$, where $|C^0|$ denotes the number of vertices of $C^0$, and $\DD(C)$ is the diameter of $C$. Actually, using known combinatorial bounds, the running time of the algorithm is $O(\DD(C)^{2/3} \log{\DD(C)})$. In particular, this bound applies when $C$ is a disk.
Cited by 0Open access
Subir Ghosh, David M. Mount · 1987
The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertices are the vertices of the obstacles and whose edges are pairs of vertices (u, v) such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. An algorithm is presented that computes the visibility graph of s set of obstacles in time O(E + n log n), where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles.
Cited by 94
Szabolcs Kovács, Gábor J. T&oaacute;th, Ralf Der · 1996
Approximation of unknown input-output mappingsby optimizing approximating functions is important for a number of practical applications. A straightforward method involves dividing the whole input space into small regions and finding the optimal approximating value within each. For such an method to work well the way the input region is divided is very important. In this paper we derive an algorithm that takes into account both the distribution of the input points and how rapidly the mapping is changing. The method is demonstrated on a simple function approximation problem. 1 Introduction The last decades showed a revolution in optimization techniques. Ever since it was understood that practically interesting problems often involve objectives with many local minima much effort has been made to develop powerful algorithms in order to find the global optimum of multi-modal functions. One of the often used algorithms is genetic algorithm (GA) [1]. It has long been esteemed for being able ...
Cited by 0
2008
Occlusion culling based on precomputed visibility information is a standard method for accelerating the rendering in real-time graphics applications. In this paper we present a new general algorithm that performs the visibility precomputation for a group of viewcells in an output-sensitive fashion. This is achieved by exploiting the directional coherence of visibility between adjacent viewcells. The algorithm is independent of the underlying from-region visibility solver and is therefore applicable to exact, conservative and aggressive visibility solvers in both 2D and 3D.
Cited by 0
Micha Sharir, Mark H. Overmars · ACM Transactions on Graphics · 1992
We derive a simple output-sensitive algorithm for hidden surface removal in a collection of n triangles in space for which a (partial) depth order is known. If k is the combinatorial complexity of the output visibility map , the method runs in time O(n √k log n). The method is extended to work for other classes of objects as well, sometimes with even improved time bounds. For example, we obtain an algorithm that performs hidden surface removal for n (nonintersecting) balls in time O(n 3/2 log n + k).
Cited by 46Open access
Frank Nielsen, Mariette Yvinec · International Journal of Computational Geometry & Applications · 1998
A set of planar objects is said to be of type m if the convex hull of any two objects has its size bounded by 2m. In this paper, we present an algorithm based on the marriage-before-conquest paradigm to compute the convex hull of a set of n planar convex objects of fixed type m. The algorithm is output-sensitive, i.e. its time complexity depends on the size h of the computed convex hull. The main ingredient of this algorithm is a linear method to find a bridge, i.e. a facet of the convex hull intersected by a given line. We obtain an O(nβ(h,m log h)-time convex hull algorithm for planar objects. Here β(h,2)=O(1) and β(h,m) is an extremely slowly growing function. As a direct consequence, we can compute in optimal Θ(n log h) time the convex hull of disks, convex homothets, non-overlapping objects. The method described in this paper also applies to compute lower envelopes of functions. In particular, we obtain an optimal Θ(n log h)-time algorithm to compute the upper envelope of line segments.
Cited by 28
Andrzej Lingas · Lecture notes in computer science · 2009
Cited by 13
Bernard Chazelle, Jiřı́ Matoušek · Computational Geometry · 1995
Cited by 51
Franck Nielsen, Mariette Yvinec · 2009
Cited by 0
James Stewart, Sherif Ghali · 1993
Given a set of polyhedra and a polygon oe in E 3 , the oe--aspect graph is a partition of the faces of the polyhedra into regions such that the area of oe that is visible from each region has the same structure or "aspect." We present an output-sensitive algorithm to compute the oe--aspect graph. In computer graphics, this problem arises in rendering images of polyhedral scenes illuminated by area light sources. This is the first analytical solution for the problem and the algorithm is simple enough to be useful in practice. 1 Introduction A problem that arises in computer graphics is the computation of the shadow boundaries of a set of polyhedra lit by a polygonal light source. The shadow boundaries are curves on the faces of the polyhedra at which there is discontinuity in the intensity of the received light. State-of-the-art radiosity-style rendering algorithms partition the polygons of the scene into somewhat arbitrary regions and compute light transmission between pairs of reg...
Cited by 0
Maria-Florina Balcan, Christopher L. Seiler, Dravyansh Sharma · arXiv (Cornell University) · 2022
Data-driven algorithm design is a promising, learning-based approach for beyond worst-case analysis of algorithms with tunable parameters. An important open problem is the design of computationally efficient data-driven algorithms for combinatorial algorithm families with multiple parameters. As one fixes the problem instance and varies the parameters, the "dual" loss function typically has a piecewise-decomposable structure, i.e. is well-behaved except at certain sharp transition boundaries. In this work we initiate the study of techniques to develop efficient ERM learning algorithms for data-driven algorithm design by enumerating the pieces of the sum dual loss functions for a collection of problem instances. The running time of our approach scales with the actual number of pieces that appear as opposed to worst case upper bounds on the number of pieces. Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes using tools from computational geometry, and an execution graph which compactly represents all the states the algorithm could attain for all possible parameter values. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.
Cited by 0Open access
George Manoussakis · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
The degeneracy of a graph G is the smallest integer k such that every subgraph of G contains a vertex of degree at most k. Given an n-order k-degenerate graph G, we present an algorithm for enumerating all its maximal cliques. Assuming that c is the number of maximal cliques of G, our algorithm has setup time O(n(k^2+s(k+1))) and enumeration time cO((k+1)f(k+1)) where s(k+1) (resp. f(k+1)) is the preprocessing time (resp. enumeration time) for maximal clique enumeration in a general (k+1)-order graph. This is the first output sensitive algorithm whose enumeration time depends only on the degeneracy of the graph.
Cited by 4Open access
Sebastiano Columbano, Komei Fukuda, Colin N. Jones · CRM proceedings & lecture notes · 2009
This paper considers the multi-parametric linear complementarity problem (pLCP) with sufficient matrices. The main result is an algorithm to find a polyhedral decomposition of the set of feasible parameters and to construct a piecewise affine function that maps each feasible parameter to a solution of the associated LCP in such a way that the function is affine over each cell of the decomposition. The algorithm is output-sensive in the sense that its time complexity is polynomial in the size of the input and linear in the size of the output, when the problem is non-degenerate. We give a lexicographic perturbation technique to resolve degeneracy as well. Unlike for the non-parametric case, the resolution turns out to be nontrivial, and in particular, it involves linear programming (LP) duality and multi-objective LP.
Cited by 13
François Le Gall · Lecture notes in computer science · 2012
Cited by 0Open access