Source author record

Alper Üngör

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Computational Complexity Data Structures and Algorithms

Catalog footprint

Research overview

4works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A Fast 2-Approximation Algorithm for Guarding Orthogonal Terrains

Terrain Guarding Problem(TGP), which is known to be NP-complete, asks to find a smallest set of guard locations on a terrain $T$ such that every point on $T$ is visible by a guard. Here, we study this problem on 1.5D orthogonal terrains where the edges are bound to be horizontal or vertical. We propose a 2-approximation algorithm that runs in O( $n \log m$ ) time, where $n$ and $m$ are the sizes of input and output, respectively. This is an improvement over the previous best algorithm, which is a 2-approximation with O( $n^2$ ) running time.

preprint2014arXiv

Finding a Curve in a Point Set

Let $P$ be a polygonal curve in $\mathbb{R}^D$ of length $n$ , and $S$ be a point set of size $k$ . The Curve/Point Set Matching problem consists of finding a polygonal curve $Q$ on $S$ such that its Fréchet distance from $P$ is less than a given $\varepsilon$ . In this paper, we consider this problem with the added freedom to transform the input curve $P$ by translating it, rotating it, or applying an arbitrary affine transform. We present exact and approximation algorithms for several variations of this problem.

preprint2014arXiv

Matching Curves to Imprecise Point Sets using Fréchet Distance

Let $P$ be a polygonal curve in $\mathbb{R}^d$ of length $n$ , and $S$ be a point-set of size $k$ . The Curve/Point Set Matching problem consists of finding a polygonal curve $Q$ on $S$ such that the Fréchet distance from $P$ is less than a given $\varepsilon$ . We consider eight variations of the problem based on the distance metric used and the omittability or repeatability of the points. We provide closure to a recent series of complexity results for the case where $S$ consists of precise points. More importantly, we formulate a more realistic version of the problem that takes into account measurement errors. This new problem is posed as the matching of a given curve to a set of imprecise points. We prove that all three variations of the problem that are in P when $S$ consists of precise points become NP-complete when $S$ consists of imprecise points. We also discuss approximation results.

preprint2012arXiv

Hardness Results on Curve/Point Set Matching with Fréchet Distance

Let P be a polygonal curve in R^d of length n, and S be a point-set of size k. We consider the problem of finding a polygonal curve Q on S such that all points in S are visited and the Fréchet distance from $P$ is less than a given epsilon. We show that this problem is NP-complete, regardless of whether or not points from S are allowed be visited more than once. However, we also show that if the problem instance satisfies certain restrictions, the problem is polynomial-time solvable, and we briefly outline an algorithm that computes Q.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.