Source author record

Alina Shaikhet

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

ResearcherUnclaimed source record

Computational Geometry

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Essential Constraints of Edge-Constrained Proximity Graphs

Given a plane forest $F = (V, E)$ of $|V| = n$ points, we find the minimum set $S \subseteq E$ of edges such that the edge-constrained minimum spanning tree over the set $V$ of vertices and the set $S$ of constraints contains $F$ . We present an $O(n \log n )$ -time algorithm that solves this problem. We generalize this to other proximity graphs in the constraint setting, such as the relative neighbourhood graph, Gabriel graph, $β$ -skeleton and Delaunay triangulation. We present an algorithm that identifies the minimum set $S\subseteq E$ of edges of a given plane graph $I=(V,E)$ such that $I \subseteq CG_β(V, S)$ for $1 \leq β\leq 2$ , where $CG_β(V, S)$ is the constraint $β$ -skeleton over the set $V$ of vertices and the set $S$ of constraints. The running time of our algorithm is $O(n)$ , provided that the constrained Delaunay triangulation of $I$ is given.

preprint2016arXiv

Probing Convex Polygons with a Wedge

Minimizing the number of probes is one of the main challenges in reconstructing geometric objects with probing devices. In this paper, we investigate the problem of using an $ω$ -wedge probing tool to determine the exact shape and orientation of a convex polygon. An $ω$ -wedge consists of two rays emanating from a point called the apex of the wedge and the two rays forming an angle $ω$ . To probe with an $ω$ -wedge, we set the direction that the apex of the probe has to follow, the line $\overrightarrow L$ , and the initial orientation of the two rays. A valid $ω$ -probe of a convex polygon $O$ contains $O$ within the $ω$ -wedge and its outcome consists of the coordinates of the apex, the orientation of both rays and the coordinates of the closest (to the apex) points of contact between $O$ and each of the rays. We present algorithms minimizing the number of probes and prove their optimality. In particular, we show how to reconstruct a convex $n$ -gon (with all internal angles of size larger than $ω$ ) using $2n-2$ $ω$ -probes; if $ω= π/2$ , the reconstruction uses $2n-3$ $ω$ -probes. We show that both results are optimal. Let $N_B$ be the number of vertices of $O$ whose internal angle is at most $ω$ , (we show that $0 \leq N_B \leq 3$ ). We determine the shape and orientation of a general convex $n$ -gon with $N_B=1$ (respectively $N_B=2$ , $N_B=3$ ) using $2n-1$ (respectively $2n+3$ , $2n+5$ ) $ω$ -probes. We prove optimality for the first case. Assuming the algorithm knows the value of $N_B$ in advance, the reconstruction of $O$ with $N_B=2$ or $N_B=3$ can be achieved with $2n+2$ probes,- which is optimal.

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.