7 papers
Decomposing a Simple Polygon with Geodesic Unit-Balls
Reilly Browne, Prahlad Narasimhan Kasthurirangan
We consider covering and partitioning a simple polygon into pieces which either have unit geodesic radius or unit geodesic diameter, using the -metric for distances. There…
Single-Criteria Metric -Dominating Set Problem via Minor-Preserving Support
Reilly Browne, Hsien-Chih Chang
Given an unweighted graph , the *minimum -dominating set problem* asks for the smallest-cardinality subset such that every vertex in is within radius of some vert…
Covering and Partitioning Complex Objects with Small Pieces
Anders Aamand, Mikkel Abrahamsen, Reilly Browne +6
We study the problems of covering or partitioning a polygon (possibly with holes) using a minimum number of small pieces, where a small piece is a connected sub-polygon contain…
An Overview of Minimum Convex Cover and Maximum Hidden Set
Reilly Browne
We give a review of results on the minimum convex cover and maximum hidden set problems. In addition, we give some new results. First we show that it is NP-hard to determine whethe…
Convex Cover and Hidden Set in Funnel Polygons
Reilly Browne
We present linear-time algorithms for both maximum hidden set and minimum convex cover in funnel polygons. These algorithms show that funnel polygons are "homestead" polygons, i.e.…
Cache-Oblivious Parallel Convex Hull in the Binary Forking Model
Reilly Browne, Rezaul Chowdhury, Shih-Yu Tsai +1
We present two cache-oblivious sorting-based convex hull algorithms in the Binary Forking Model. The first is an algorithm for a presorted set of points which achieves work,…
Fast American Option Pricing using Nonlinear Stencils
Zafar Ahmad, Reilly Browne, Rezaul Chowdhury +3
We study the binomial, trinomial, and Black-Scholes-Merton models of option pricing. We present fast parallel discrete-time finite-difference algorithms for American call option pr…