1,720,966 research outputs found
Algorithms for the discrete Fréchet distance under translation
No full textThe (discrete) \frechet\ distance (DFD) is a popular similarity measure for curves. Often the input curves are not aligned, so one of them must undergo some transformation for the distance computation to be meaningful. Ben Avraham et al. (2015) presented an -time algorithm for DFD between two sequences of points of sizes and in the plane under translation. In this paper we consider two variants of DFD, both under translation.For DFD with shortcuts in the plane, we present an -time algorithm, by presenting a dynamic data structure for reachability queries in the underlying directed graph. In 1D, we show how to avoid the use of parametric search and remove a logarithmic factor from the running time of (the 1D versions of) these algorithms and of an algorithm for the weak discrete \frechet\ distance; the resulting running times are thus , for the discrete \frechet\ distance, , for the shortcuts variant, and for the weak variant.Our 1D algorithms follow a general scheme introduced by Martello et al. (1984) for the Balanced Optimization Problem (BOP), which is especially useful when an efficient dynamic version of the feasibility decider is available. We present an alternative scheme for BOP, whose advantage is that it yields efficient algorithms quite easily, without having to devise a specially tailored dynamic version of the feasibility decider. We demonstrate our scheme on the most uniform path problem (significantly improving the known bound), and observe that weak DFD under translation in 1D is a special case of it
Condorcet Relaxation In Spatial Voting
No full textConsider a set of voters V, represented by a multiset in a metric space (X,d). The voters have to reach a decision - a point in X. A choice p∈ X is called a β-plurality point for V, if for any other choice q∈ X it holds that |{v∈ V ∣ β⋅ d(p,v)≤ d(q,v)}| ≥|V|/2 . In other words, at least half of the voters ``prefer'' over q, when an extra factor of β is taken in favor of p.
For β=1, this is equivalent to Condorcet winner, which rarely exists. The concept of β-plurality was suggested by Aronov, de Berg, Gudmundsson, and Horton [SoCG 2020] as a relaxation of the Condorcet criterion.
Denote by β*(X,d) the value sup{ β ∣ every finite multiset V in X admits a β-plurality point}}.
The parameter β* determines the amount of relaxation required in order to reach a stable decision.
Aronov et al. showed that for the Euclidean plane β*(ℝ2,\|⋅\|2)=√3/2 , and more generally, for d-dimensional Euclidean space, 1/√d ≤ β*(ℝd,\|⋅\|2)≤√3/2 .
In this paper, we show that 0.557≤ β*(ℝd,\|⋅\|2) for any dimension d (notice that 1/√
Plurality in Spatial Voting Games with constant
Full text linkConsider a set of voters, represented by a multiset in a metric space
. The voters have to reach a decision -- a point in . A choice is called a -plurality point for , if for any other choice it holds that . In other words, at least half of the voters
``prefer'' over , when an extra factor of is taken in favor of
. For , this is equivalent to Condorcet winner, which rarely
exists. The concept of -plurality was suggested by Aronov, de Berg,
Gudmundsson, and Horton [TALG 2021] as a relaxation of the Condorcet criterion.
Let \beta^*_{(X,d)}=\sup\{\beta\mid \mbox{every finite multiset VX\beta-plurality point}\}. The parameter determines the
amount of relaxation required in order to reach a stable decision. Aronov et
al. showed that for the Euclidean plane
, and more generally,
for -dimensional Euclidean space, . In this paper, we
show that for any dimension
(notice that for any ). In addition, we
prove that for every metric space it holds that
, and show that there exists a metric space for
which
Algorithms for the Discrete Fréchet Distance Under Translation
Full text linkThe (discrete) Fréchet distance (DFD) is a popular similarity measure for curves. Often the input curves are not aligned, so one of them must undergo some transformation for the distance computation to be meaningful. Ben Avraham et al. [Rinat Ben Avraham et al., 2015] presented an O(m^3n^2(1+log(n/m))log(m+n))-time algorithm for DFD between two sequences of points of sizes m and n in the plane under translation. In this paper we consider two variants of DFD, both under translation.
For DFD with shortcuts in the plane, we present an O(m^2n^2 log^2(m+n))-time algorithm, by presenting a dynamic data structure for reachability queries in the underlying directed graph. In 1D, we show how to avoid the use of parametric search and remove a logarithmic factor from the running time of (the 1D versions of) these algorithms and of an algorithm for the weak discrete Fréchet distance; the resulting running times are thus O(m^2n(1+log(n/m))), for the discrete Fréchet distance, and O(mn log(m+n)), for its two variants.
Our 1D algorithms follow a general scheme introduced by Martello et al. [Martello et al., 1984] for the Balanced Optimization Problem (BOP), which is especially useful when an efficient dynamic version of the feasibility decider is available. We present an alternative scheme for BOP, whose advantage is that it yields efficient algorithms quite easily, without having to devise a specially tailored dynamic version of the feasibility decider. We demonstrate our scheme on the most uniform path problem (significantly improving the known bound), and observe that the weak DFD under translation in 1D is a special case of it
Approximate Nearest Neighbor for Curves - Simple, Efficient, and Deterministic
Full text linkIn the (1+ε,r)-approximate near-neighbor problem for curves (ANNC) under some similarity measure δ, the goal is to construct a data structure for a given set of curves that supports approximate near-neighbor queries: Given a query curve Q, if there exists a curve C ∈ such that δ(Q,C)≤ r, then return a curve C' ∈ with δ(Q,C') ≤ (1+ε)r. There exists an efficient reduction from the (1+ε)-approximate nearest-neighbor problem to ANNC, where in the former problem the answer to a query is a curve C ∈ with δ(Q,C) ≤ (1+ε)⋅δ(Q,C^*), where C^* is the curve of most similar to Q.
Given a set of n curves, each consisting of m points in d dimensions, we construct a data structure for ANNC that uses n⋅ O(1/ε)^{md} storage space and has O(md) query time (for a query curve of length m), where the similarity measure between two curves is their discrete Fréchet or dynamic time warping distance. Our method is simple to implement, deterministic, and results in an exponential improvement in both query time and storage space compared to all previous bounds.
Further, we also consider the asymmetric version of ANNC, where the length of the query curves is k ≪ m, and obtain essentially the same storage and query bounds as above, except that m is replaced by k. Finally, we apply our method to a version of approximate range counting for curves and achieve similar bounds
A constant-factor approximation algorithm for vertex guarding a WV-polygon
No full textThe problem of vertex guarding a simple polygon was first studied by Subir K. Ghosh (1987), who presented a polynomial-time -approximation algorithm for placing as few guards as possible at vertices of a simple -gon , such that every point in is visible to at least one of the guards. Ghosh also conjectured that this problem admits a polynomial-time algorithm with constant approximation ratio. Due to the centrality of guarding problems in the field of computational geometry, much effort has been invested throughout the years in trying to resolve this conjecture. Despite some progress (surveyed below), the conjecture remains unresolved to date.In this paper, we confirm the conjecture for the important case of weakly visible polygons, by presenting a (2+\eps)-approximation algorithm for guarding such a polygon using vertex guards. A simple polygon is \emph{weakly visible} if it has an edge , such that every point in is visible from some point on . We also present a (2+\eps)-approximation algorithm for guarding a weakly visible polygon , where guards may be placed anywhere on \u27s boundary (except in the interior of the edge ). Finally, we present an -approximation algorithm for vertex guarding a polygon that is weakly visible from a chord.
Our algorithms are based on an in-depth analysis of the geometric properties of the regions that remain unguarded after placing guards at the vertices to guard the polygon\u27s boundary. Finally, our algorithms may become useful as part of the grand attempt of Bhattacharya et al. to prove the original conjecture, as their approach is based on partitioning the underlying simple polygon into a hierarchy of weakly visible polygons
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
