30 citations · 82 across the 38 of their papers we have counts for
5 papers · 1 filter
Visibility Queries in Simple Polygons
Sujoy Bhore, Chih-Hung Liu, Anurag Murty Naredla +6
Given a simple polygon with vertices, we consider the problem of constructing a data structure for visibility queries: for any query point , compute the visibility…
Optimal-Cost Construction of Shallow Cuttings for 3-D Dominance Ranges in the I/O-Model
Yakov Nekrich, Saladi Rahul
Shallow cuttings are a fundamental tool in computational geometry and spatial databases for solving offline and online range searching problems. For a set of points in 3-D,…
Convexity Helps Iterated Search in 3D
Peyman Afshani, Yakov Nekrich, Frank Staals
Inspired by the classical fractional cascading technique, we introduce new techniques to speed up the following type of iterated search in 3D: The input is a graph wit…
Finding a Maximum Clique in a Grounded 1-Bend String Graph
J. Mark Keil, Debajyoti Mondal, Ehsan Moradi +1
A grounded 1-bend string graph is an intersection graph of a set of polygonal lines, each with one bend, such that the lines lie above a common horizontal line and have exac…
Orthogonal Point Location and Rectangle Stabbing Queries in 3-d
Timothy M. Chan, Yakov Nekrich, Saladi Rahul +1
In this work, we present a collection of new results on two fundamental problems in geometric data structures: orthogonal point location and rectangle stabbing. -We give the first…