ML p(r)ior | Distance-Sensitive Planar Point Location

Distance-Sensitive Planar Point Location

2016-02-02
Let $\mathcal{S}$ be a connected planar polygonal subdivision with $n$ edges that we want to preprocess for point-location queries, and where we are given the probability $\gamma_i$ that the query point lies in a polygon $P_i$ of $\mathcal{S}$. We show how to preprocess $\mathcal{S}$ such that the query time for a point~$p\in P_i$ depends on~$\gamma_i$ and, in addition, on the distance from $p$ to the boundary of~$P_i$---the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time $O\left(\min \left(\log n, 1 + \log \frac{\mathrm{area}(P_i)}{\gamma_i \Delta_{p}^2}\right)\right)$, where $\Delta_{p}$ is the shortest Euclidean distance of the query point~$p$ to the boundary of $P_i$. Our structure uses $O(n)$ space and $O(n \log n)$ preprocessing time. It is based on a decomposition of the regions of $\mathcal{S}$ into convex quadrilaterals and triangles with the following property: for any point $p\in P_i$, the quadrilateral or triangle containing~$p$ has area $\Omega(\Delta_{p}^2)$. For the special case where $\mathcal{S}$ is a subdivision of the unit square and $\gamma_i=\mathrm{area}(P_i)$, we present a simpler solution that achieves a query time of $O\left(\min \left(\log n, \log \frac{1}{\Delta_{p}^2}\right)\right)$. The latter solution can be extended to convex subdivisions in three dimensions.
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2018-09-27
1809.10531 | cs.CG

In the range closest pair problem, we want to construct a data structure storing a set $S$ of $n$ po… show more
PDF

Highlights - Most important sentences from the article

2019-05-07

In this paper we study two geometric data structure problems in the special case when input objects … show more
PDF

Highlights - Most important sentences from the article

2018-07-25
1807.09498 | cs.CG

We consider a range-search variant of the closest-pair problem. Let $\varGamma$ be a fixed shape in … show more
PDF

Highlights - Most important sentences from the article

2018-07-16

We consider exact distance oracles for directed weighted planar graphs in the presence of failing ve… show more
PDF

Highlights - Most important sentences from the article

2017-10-30

Let $P$ be a set of $n$ points in the plane. We compute the value of $\theta\in [0,2\pi)$ for which … show more
PDF

Highlights - Most important sentences from the article

2019-04-24

We study two fundamental problems dealing with curves in the plane, namely, the nearest-neighbor pro… show more
PDF

Highlights - Most important sentences from the article

2018-09-20
1809.07481 | cs.CG

Let $P$ be a simple polygon of $n$ vertices. We consider two-point $L_1$ shortest path queries in $P… show more
PDF

Highlights - Most important sentences from the article

2018-03-21
1803.07773 | cs.CG

A stay point of a moving entity is a region in which it spends a significant amount of time. In this… show more
PDF

Highlights - Most important sentences from the article

2019-03-04
1903.01417 | cs.CG

Let $\mathcal{P}$ be a polygonal domain of $h$ holes and $n$ vertices. We study the problem of const… show more
PDF

Highlights - Most important sentences from the article

2018-09-27
1809.10495 | cs.CG

We study the point location problem in incremental (possibly disconnected) planar subdivisions, that… show more
PDF

Highlights - Most important sentences from the article

2018-11-05

We present new tradeoffs between space and query-time for exact distance oracles in directed weighte… show more
PDF

Highlights - Most important sentences from the article

2018-09-26
1809.09792 | cs.CG

We consider a repulsion actuator located in an $n$-sided convex environment full of point particles.… show more
PDF

Highlights - Most important sentences from the article

2018-07-24
1807.09392 | cs.CG

Most path planning problems among polygonal obstacles ask to find a path that avoids the obstacles a… show more
PDF

Highlights - Most important sentences from the article

2018-10-01
1810.00715 | cs.CG

We present self-adjusting data structures for answering point location queries in convex and connect… show more
PDF

Highlights - Most important sentences from the article

2018-07-26

We study augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the lar… show more
PDF

Highlights - Most important sentences from the article

2016-07-19
1607.05527 | cs.CG

Given a simple polygon $\mathcal{P}$ on $n$ vertices, two points $x,y$ in $\mathcal{P}$ are said to … show more
PDF

Highlights - Most important sentences from the article