Source author record

Mojtaba Nouri Bygi

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

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2013arXiv

Near Optimal Line Segment Weak Visibility Queries in Simple Polygons

This paper considers the problem of computing the weak visibility polygon (WVP) of any query line segment pq (or WVP(pq)) inside a given simple polygon P. We present an algorithm that preprocesses P and creates a data structure from which WVP(pq) is efficiently reported in an output sensitive manner. Our algorithm needs O(n^2 log n) time and O(n^2) space in the preprocessing phase to report WVP(pq) of any query line segment pq in time O(log^2 n + |WVP(pq)|). We improve the preprocessing time and space of current results for this problem at the expense of more query time.

preprint2013arXiv

Weak Visibility Queries of Line Segments in Simple Polygons and Polygonal Domains

In this paper we consider the problem of computing the weak visibility polygon of any query line segment $pq$ (or $WVP(pq)$ ) inside a given polygon $P$ . Our first non-trivial algorithm runs in simple polygons and needs $O(n^3 \log n)$ time and $O(n^3)$ space in the preprocessing phase to report $WVP(pq)$ of any query line segment $pq$ in time $O(\log n + |WVP(pq)|)$ . We also give an algorithm to compute the weak visibility polygon of a query line segment in a non-simple polygon with $h$ pairwise-disjoint polygonal obstacles with a total of $n$ vertices. Our algorithm needs $O(n^2 \log n)$ time and $O(n^2)$ space in the preprocessing phase and computes $WVP(pq)$ in query time of $O(n\hbar \log n + k)$ , in which $\hbar$ is an output sensitive parameter of at most $\min(h,k)$ , and $k = O(n^2h^2)$ is the output size. This is the best query-time result on this problem so far.

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.