BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

André van Renssen

André van Renssen contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Geometry

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
1topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2024arXiv

Generalized Sweeping Line Spanners

We present sweeping line graphs, a generalization of $Θ$-graphs. We show that these graphs are spanners of the complete graph, as well as of the visibility graph when line segment constraints or polygonal obstacles are considered. Our proofs use general inductive arguments to make the step to the constrained setting. These same arguments could apply to other spanner constructions in the unconstrained setting, removing the need to find separate proofs that they are spanning in the constrained and polygonal obstacle settings.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Covering a set of line segments with a few squares

We study three covering problems in the plane. Our original motivation for these problems come from trajectory analysis. The first is to decide whether a given set of line segments can be covered by up to four unit-sized, axis-parallel squares. The second is to build a data structure on a trajectory to efficiently answer whether any query subtrajectory is coverable by up to three unit-sized axis-parallel squares. The third problem is to compute a longest subtrajectory of a given trajectory that can be covered by up to two unit-sized axis-parallel squares.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Local Routing in Sparse and Lightweight Geometric Graphs

Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no $O(1)$-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin [Online routing in triangulations. SIAM Journal on Computing, 33(4):937-951, 2004] showed that there exists an online routing algorithm that is $O(1)$-competitive. However, a Delaunay triangulation can have $Ω(n)$ vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set $V$ of $n$ points in the Euclidean plane, of a planar geometric graph on $V$ that has small weight (within a constant factor of the weight of a minimum spanning tree on $V$), constant degree, and that admits a local routing strategy that is $O(1)$-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an $O(1)$-competitive routing strategy.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Constrained Routing Between Non-Visible Vertices

In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to route. Specifically, we study routing strategies in the presence of constraints which are obstacles that edges of the graph are not allowed to cross. Let $P$ be a set of $n$ points in the plane and let $S$ be a set of line segments whose endpoints are in $P$, with no two line segments intersecting properly. We present the first deterministic 1-local $O(1)$-memory routing algorithm that is guaranteed to find a path between two vertices in the visibility graph of $P$ with respect to a set of constraints $S$. The strategy never looks beyond the direct neighbors of the current node and does not store more than $O(1)$-information to reach the target. We then turn our attention to finding competitive routing strategies. We show that when routing on any triangulation $T$ of $P$ such that $S\subseteq T$, no $o(n)$-competitive routing algorithm exists when the routing strategy restricts its attention to the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an $O(n)$-competitive deterministic 1-local $O(1)$-memory routing algorithm on any such $T$, which is optimal in the worst case, given the lower bound.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access