LOGIN TO YOUR ACCOUNT

Username
Password
Remember Me
Or use your Academic/Social account:

CREATE AN ACCOUNT

Or use your Academic/Social account:

Congratulations!

You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.

Important!

Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message

CREATE AN ACCOUNT

Name:
Username:
Password:
Verify Password:
E-mail:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1

Discovery Projects - Grant ID: DP150101134

Title
Discovery Projects - Grant ID: DP150101134
Funding
ARC | Discovery Projects
Contract (GA) number
DP150101134
Start Date
2015/01/01
End Date
2017/12/31
Open Access mandate
no
Organizations
-
More information
http://purl.org/au-research/grants/arc/DP150101134

 

  • Fast Frechet Distance Between Curves With Long Edges

    Gudmundsson, Joachim; Mirzanezhad, Majid; Mohades, Ali; Wenk, Carola (2017)
    Projects: ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134)
    Computing the~\Frd\ between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fr\'echet distance computations become easier. Let $P$ and $Q$ be two polygonal curves in $\Reals^d$ with $n$ and $m$ vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fr\'echet distance between them: (1) a linear-time algorithm for deciding the Fr\'echet distance between two curves, (2) an ...

    Spatio-Temporal Analysis of Team Sports -- A Survey

    Gudmundsson, Joachim; Horton, Michael (2016)
    Projects: ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134)
    Team-based invasion sports such as football, basketball and hockey are similar in the sense that the players are able to move freely around the playing area; and that player and team performance cannot be fully analysed without considering the movements and interactions of all players as a group. State of the art object tracking systems now produce spatio-temporal traces of player trajectories with high definition and high frequency, and this, in turn, has facilitated a variety of research ef...

    Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees

    Große, Ulrike; Gudmundsson, Joachim; Knauer, Christian; Smid, Michiel; Stehn, Fabian (2016)
    Projects: ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134)
    We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n \log^3 n) time, and (ii) the input graph is a tree, running in O(n^2 \log n) time. We also present an algorithm that computes a (1+\eps)-approximation in O(n + 1/\eps^3) time, for paths in R^d, where d is a constant.

    Shortcuts for the Circle

    Bae, Sang Won; de Berg, Mark; Cheong, Otfried; Gudmundsson, Joachim; Levcopoulos, Christos (2016)
    Projects: ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134)
    Let $C$ be the unit circle in $\mathbb{R}^2$. We can view $C$ as a plane graph whose vertices are all the points on $C$, and the distance between any two points on $C$ is the length of the smaller arc between them. We consider a graph augmentation problem on $C$, where we want to place $k\geq 1$ \emph{shortcuts} on $C$ such that the diameter of the resulting graph is minimized. We analyze for each $k$ with $1\leq k\leq 7$ what the optimal set of shortcuts is. Interestingly, the minimum diamet...

    Range-Efficient Consistent Sampling and Locality-Sensitive Hashing for Polygons

    Gudmundsson, Joachim; Pagh, Rasmus (2017)
    Projects: ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134), EC | SSS (614331)
    Locality-sensitive hashing (LSH) is a fundamental technique for similarity search and similarity estimation in high-dimensional spaces. The basic idea is that similar objects should produce hash collisions with probability significantly larger than objects with low similarity. We consider LSH for objects that can be represented as point sets in either one or two dimensions. To make the point sets finite size we consider the subset of points on a grid. Directly applying LSH (e.g. m...

    Stable Matching with Uncertain Linear Preferences

    Aziz, Haris; Biró, Péter; Gaspers, Serge; de Haan, Ronald; Mattei, Nicholas; Rastegari, Baharak (2016)
    Projects: ARC | Future Fellowships - Grant ID: FT140100048 (FT140100048), ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134)
    We consider the two-sided stable matching setting in which there may be uncertainty about the agents' preferences due to limited information or communication. We consider three models of uncertainty: (1) lottery model --- in which for each agent, there is a probability distribution over linear preferences, (2) compact indifference model --- for each agent, a weak preference order is specified and each linear order compatible with the weak order is equally likely and (3) joint probability mode...

    On Satisfiability Problems with a Linear Structure

    Gaspers, Serge; Papadimitriou, Christos; Saether, Sigve Hortemo; Telle, Jan Arne (2016)
    Projects: ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134), ARC | Future Fellowships - Grant ID: FT140100048 (FT140100048)
    It was recently shown [Sæther, Telle, and Vatshelle, JAIR 54, 2015] that satisfiability is polynomially solvable when the incidence graph is an interval bipartite graph (an interval graph turned into a bipartite graph by omitting all edges within each partite set). Here we relax this condition in several directions: First, we show an FPT algorithm parameterized by k for k-interval bigraphs, bipartite graphs which can be converted to interval bipartite graphs by adding to each node of one side...

    Linearly $\chi$-Bounding $(P_6,C_4)$-Free Graphs

    Given two graphs $H_1$ and $H_2$, a graph $G$ is $(H_1,H_2)$-free if it contains no subgraph isomorphic to $H_1$ or $H_2$. Let $P_t$ and $C_s$ be the path on $t$ vertices and the cycle on $s$ vertices, respectively. In this paper we show that for any $(P_6,C_4)$-free graph $G$ it holds that $\chi(G)\le \frac{3}{2}\omega(G)$, where $\chi(G)$ and $\omega(G)$ are the chromatic number and clique number of $G$, respectively. %Our bound is attained by $C_5$ and the Petersen graph. Our bound is atta...

    Exact Algorithms via Multivariate Subroutines

    We consider the family of $\Phi$-Subset problems, where the input consists of an instance $I$ of size $N$ over a universe $U_I$ of size $n$ and the task is to check whether the universe contains a subset with property $\Phi$ (e.g., $\Phi$ could be the property of being a feedback vertex set for the input graph of size at most $k$). Our main tool is a simple randomized algorithm which solves $\Phi$-Subset in time $(1+b-\frac{1}{c})^n N^{O(1)}$, provided that there is an algorithm for the $\Phi...

    Barrier Coverage with Non-uniform Lengths to Minimize Aggregate Movements

    Gaspers, Serge; Gudmundsson, Joachim; Mestre, Julián; Rümmele, Stefan (2017)
    Projects: ARC | Future Fellowships - Grant ID: FT140100048 (FT140100048), ARC | Discovery Projects - Grant ID: DP150101134 (DP150101134)
    Given a line segment $I=[0,L]$, the so-called barrier, and a set of $n$ sensors with varying ranges positioned on the line containing $I$, the barrier coverage problem is to move the sensors so that they cover $I$, while minimising the total movement. In the case when all the sensors have the same radius the problem can be solved in $O(n \log n)$ time (Andrews and Wang, Algorithmica 2017). If the sensors have different radii the problem is known to be NP-hard to approximate within a constant ...
  • No project research data found
  • Scientific Results

    Chart is loading... It may take a bit of time. Please be patient and don't reload the page.

    PUBLICATIONS BY ACCESS MODE

    Chart is loading... It may take a bit of time. Please be patient and don't reload the page.

    Publications in Repositories

    Chart is loading... It may take a bit of time. Please be patient and don't reload the page.

Share - Bookmark

App Box