License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2016.32
URN: urn:nbn:de:0030-drops-68676
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6867/
Banik, Aritra ;
Panolan, Fahad ;
Raman, Venkatesh ;
Sahlot, Vibha
Fréchet Distance Between a Line and Avatar Point Set
Abstract
Frechet distance is an important geometric measure that captures the distance between two curves or more generally point sets. In this paper, we consider a natural variant of Frechet distance problem with multiple choice, provide an approximation algorithm and address its parameterized and kernelization complexity. A multiple choice problem consists of a set of color classes Q={Q_1,Q_2,...,Q_n}, where each class Q_i consists of a pair of points Q_i = {q_i, bar{q_i}}. We call a subset A subset {q_i , bar{q_i}:1 <= i <= n} conflict free if A contains at most one point from each color class. The standard objective in multiple choice problem is to select a conflict free subset that optimizes a given function.
Given a line segment l and set Q of a pair of points in R^2, our objective is to find a conflict free subset that minimizes the Frechet distance between l and the point set, where the minimum is taken over all possible conflict free subsets. We first show that this problem is NP-hard, and provide a 3-approximation algorithm. Then we develop a simple randomized FPT algorithm which is later derandomized using universal family of sets. We believe that this technique can be of independent interest, and can be used to solve other parameterized multiple choice problems. The randomized algorithm runs in O(2^k * n * log^2(n)) time, and the derandomized deterministic algorithm runs in O(2^k * k^{O(log(k))} * n * log^2(n)) time, where k, the parameter, is the number of elements in the conflict free subset solution. Finally we present a simple branching algorithm for the problem running in O(2^k * n^{2} *log(n)) time. We also show that the problem is unlikely to have a polynomial sized kernel under standard complexity theoretic assumption.
BibTeX - Entry
@InProceedings{banik_et_al:LIPIcs:2016:6867,
author = {Aritra Banik and Fahad Panolan and Venkatesh Raman and Vibha Sahlot},
title = {{Fr{\'e}chet Distance Between a Line and Avatar Point Set}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {32:1--32:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-027-9},
ISSN = {1868-8969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6867},
URN = {urn:nbn:de:0030-drops-68676},
doi = {10.4230/LIPIcs.FSTTCS.2016.32},
annote = {Keywords: Frechet Distance, Avatar Problems, Multiple Choice, FPT}
}
|
Keywords: |
|
Frechet Distance, Avatar Problems, Multiple Choice, FPT |
|
Collection: |
|
36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.12.2016 |
