### Distance-Sensitive Planar Point Location

**2016-02-02**

1602.00767 | cs.CG

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.

**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

**2019-05-07**

1905.02322 | cs.DS

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

**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

**2018-07-16**

1807.05968 | cs.DS

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

**2017-10-30**

1710.10888 | cs.CG

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

**2019-04-24**

1904.11026 | cs.CG

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

**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

**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

**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

**2018-09-27**

1809.10495 | cs.CG

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

**2018-11-05**

1811.01551 | cs.DS

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

**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

**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

**2018-10-01**

1810.00715 | cs.CG

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

**2018-07-26**

1807.10093 | cs.CG

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

**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