research
∙
08/14/2023
Online Class Cover Problem
In this paper, we study the online class cover problem where a (finite o...
share
research
∙
07/11/2023
Distance-Preserving Graph Compression Techniques
We study the problem of distance-preserving graph compression for weight...
research
∙
11/10/2021
Approximating bottleneck spanning trees on partitioned tuples of points
We present approximation algorithms for the following NP-hard optimizati...
research
∙
09/15/2021
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
Given two sets S and T of points in the plane, of total size n, a many-t...
research
∙
09/05/2021
A linear-time algorithm for semitotal domination in strongly chordal graphs
In a graph G=(V,E) with no isolated vertex, a dominating set D ⊆ V, is c...
research
∙
07/09/2021
Constant Delay Lattice Train Schedules
The following geometric vehicle scheduling problem has been considered: ...
research
∙
04/13/2020
A Simple Randomized O(n log n)–Time Closest-Pair Algorithm in Doubling Metrics
Consider a metric space (P,dist) with N points whose doubling dimension ...
research
∙
09/13/2019
Linear Size Planar Manhattan Network for Convex Point Sets
Let G = (V, E) be an edge-weighted geometric graph such that every edge ...
research
∙
09/09/2019
Maximum Bipartite Subgraph of Geometric Intersection Graphs
We study the Maximum Bipartite Subgraph(MBS) problem, which is defined a...
research
∙
06/27/2019
Packing Boundary-Anchored Rectangles and Squares
Consider a set P of n points on the boundary of an axis-aligned square Q...
research
∙
05/13/2019
Color spanning Localized query
Let P be a set of n points and each of the points is colored with one of...
research
∙
05/02/2019
Flip Distance to some Plane Configurations
We study an old geometric optimization problem in the plane. Given a per...
research
∙
03/17/2019
Computing Maximum Independent Set on Outerstring Graphs and Their Relatives
A graph G with n vertices is called an outerstring graph if it has an in...
research
∙
10/22/2018
On the Minimum Consistent Subset Problem
Let P be a set of n colored points in the plane. Introduced by Hart (196...
research
∙
09/27/2018
Plane and Planarity Thresholds for Random Geometric Graphs
A random geometric graph, G(n,r), is formed by choosing n points indepen...
research
∙
09/26/2018
Approximability of Covering Cells with Line Segments
In COCOA 2015, Korman et al. studied the following geometric covering pr...
research
∙
09/24/2018
Rectilinear Shortest Paths Among Transient Obstacles
This paper presents an optimal Θ(n n) algorithm for determining time-mi...
research
∙
08/06/2018
Time-Dependent Shortest Path Queries Among Growing Discs
The determination of time-dependent collision-free shortest paths has re...
research
∙
03/16/2018
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
We consider the Minimum Dominating Set (MDS) problem on the intersection...
research
∙
03/16/2018
Approximating Dominating Set on Intersection Graphs of L-frames
We consider the Dominating Set (DS) problem on the intersection graphs o...
research
∙
02/26/2018
Faster Algorithms for some Optimization Problems on Collinear Points
We propose faster algorithms for the following three optimization proble...
research
∙
07/29/2017
Expanding Visibility Polygons by Mirrors upto at least K units
We consider extending visibility polygon (VP) of a given point q (VP(q))...
research
∙
06/25/2017
Compatible 4-Holes in Point Sets
Counting interior-disjoint empty convex polygons in a point set is a typ...
research
∙
11/19/2013
Analysis of Farthest Point Sampling for Approximating Geodesics in a Graph
A standard way to approximate the distance between any two vertices p an...
research
∙
12/07/2012
Similarity of Polygonal Curves in the Presence of Outliers
The Fréchet distance is a well studied and commonly used measure to capt...
research
∙
02/15/2011
An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains
We present the first polynomial time approximation algorithm for computi...
research
∙
12/15/2010