J. Keil

activity

20182022

collaborators

6 papers

cs.CG2022

Improved and Generalized Algorithms for Burning a Planar Point Set

Prashant Gokhale, J. Mark Keil, Debajyoti Mondal

Given a set $P$ of points in the plane, a point burning process is a discrete time process to burn all the points of $P$ where fires must be initiated at the given points. Specific…

cs.CG2021

Bottleneck Convex Subsets: Finding $k$ Large Convex Sets in a Point Set

Stephane Durocher, J. Mark Keil, Saeed Mehrabi +1

Chvátal and Klincsek (1980) gave an $O (n^{3})$ -time algorithm for the problem of finding a maximum-cardinality convex subset of an arbitrary given set $P$ of $n$ points in the plane.…

cs.CG2021

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…

cs.CG2018

Polygon Simplification by Minimizing Convex Corners

Yeganeh Bahoo, Stephane Durocher, J. Mark Keil +3

Let $P$ be a polygon with $r > 0$ reflex vertices and possibly with holes and islands. A subsuming polygon of $P$ is a polygon $P^{'}$ such that $P \subseteq P^{'}$ , each connected compone…

cs.CG2018

Boundary Labeling for Rectangular Diagrams

Prosenjit Bose, Paz Carmi, J. Mark Keil +2

Given a set of $n$ points (sites) inside a rectangle $R$ and $n$ points (label locations or ports) on its boundary, a boundary labeling problem seeks ways of connecting every site…

cs.DS2018

Swapping Colored Tokens on Graphs

Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil +5

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. Each pair of adjacent vertices ca…