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

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

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

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

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 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 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 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 Highlights - Most important sentences from the article 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 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 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 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 Highlights - Most important sentences from the article 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 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

Highlights - Most important sentences from the article