Source author record

Marcel Roeloffzen

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

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Segment Visibility Counting Queries in Polygons

Let $P$ be a simple polygon with $n$ vertices, and let $A$ be a set of $m$ points or line segments inside $P$ . We develop data structures that can efficiently count the number of objects from $A$ that are visible to a query point or a query segment. Our main aim is to obtain fast, $O(\mathop{\textrm{polylog}} nm$ ), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves $O(\log nm)$ query time using $O(nm^2)$ space. In case $A$ also contains only points, we present a smaller, $O(n + m^{2 + \varepsilon}\log n)$ -space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and $A$ contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve $O(\log n\log nm)$ query time using only $O(nm^{2 + \varepsilon} + n^2)$ space. Finally, we show that we can even handle the case where the objects in $A$ are segments with the same bounds.

preprint2020arXiv

Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of $n$ vertices and $h$ holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $\min \{\,O(n^ω), O(n^2 + nh \log h + χ^2)\,\}$ time, where $ω<2.373$ denotes the matrix multiplication exponent and $χ\in Ω(n)\cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.

preprint2016arXiv

Distance-Sensitive Planar Point Location

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 $γ_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~ $γ_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)}{γ_i Δ_{p}^2}\right)\right)$ , where $Δ_{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 $Ω(Δ_{p}^2)$ . For the special case where $\mathcal{S}$ is a subdivision of the unit square and $γ_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}{Δ_{p}^2}\right)\right)$ . The latter solution can be extended to convex subdivisions in three dimensions.

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.