Source author record

Ji-Won Park

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics math.CO physics.data-an physics.soc-ph q-fin.GN

Catalog footprint

Research overview

2works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Obstructing Visibilities with One Obstacle

Obstacle representations of graphs have been investigated quite intensely over the last few years. We focus on graphs that can be represented by a single obstacle. Given a (topologically open) polygon $C$ and a finite set $P$ of points in general position in the complement of $C$ , the visibility graph $G_C(P)$ has a vertex for each point in $P$ and an edge $pq$ for any two points $p$ and $q$ in $P$ that can see each other, that is, $\overline{pq} \cap C=\emptyset$ . We draw $G_C(P)$ straight-line. Given a graph $G$ , we want to compute an obstacle representation of $G$ , that is, an obstacle $C$ and a set of points $P$ such that $G=G_C(P)$ . The complexity of this problem is open, even for the case that the points are exactly the vertices of a simple polygon and the obstacle is the complement of the polygon-the simple-polygon visibility graph problem. There are two types of obstacles; an inside obstacle lies in a bounded component of the complement of the visibility drawing, whereas an outside obstacle lies in the unbounded component. We show that the class of graphs with an inside-obstacle representation is incomparable with the class of graphs that have an outside-obstacle representation. We further show that any graph with at most seven vertices or circumference at most 6 has an outside-obstacle representation, which does not hold for a specific graph with 8 vertices and circumference 8. Finally, we consider the outside-obstacle graph sandwich problem: given graphs $G$ and $H$ on the same vertex set, is there a graph $K$ such that $G \subseteq K \subseteq H$ and $K$ has an outside-obstacle representation? We show that this problem is NP-hard even for co-bipartite graphs. With slight modifications, our proof also shows that the inside-obstacle graph sandwich problem, the single-obstacle graph sandwich problem, and the simple-polygon visibility graph sandwich problem are all NP-hard.

preprint2012arXiv

Permit Allocation in Emissions Trading using the Boltzmann Distribution

In emissions trading, the initial allocation of permits is an intractable issue because it needs to be essentially fair to the participating countries. There are many ways to distribute a given total amount of emissions permits among countries, but the existing distribution methods, such as auctioning and grandfathering, have been debated. In this paper we describe a new method for allocating permits in emissions trading using the Boltzmann distribution. We introduce the Boltzmann distribution to permit allocation by combining it with concepts in emissions trading. We then demonstrate through empirical data analysis how emissions permits can be allocated in practice among participating countries. The new allocation method using the Boltzmann distribution describes the most probable, natural, and unbiased distribution of emissions permits among multiple countries. Simple and versatile, this new method holds potential for many economic and environmental applications.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.