5 papers
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,…
Online computation of normalized substring complexity
Gregory Kucherov, Yakov Nekrich
The normalized substring complexity of a string is defined as , where is the number of \textit{distinct} substrings of length . This simply define…
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…
Incremental Planar Nearest Neighbor Queries with Optimal Query Time
John Iacono, Yakov Nekrich
In this paper we show that two-dimensional nearest neighbor queries can be answered in optimal time while supporting insertions in time. No p…