BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Man-Kwun Chiu

Man-Kwun Chiu contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryComputational Complexitymath.CODiscrete Mathematics

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
6works
0followers
4topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

6 published item(s)

preprint2022arXiv

Coloring circle arrangements: New $4$-chromatic planar graphs

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most $3$. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of arrangements of (pseudo-)circles. In this paper the conjecture is verified for $\triangle$-saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps $\triangle$-saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This "corona" construction has similarities with the crowning construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We also investigate fractional colorings. It is shown that the arrangement graph of every arrangement $\mathcal{A}$ of pairwise intersecting pseudocircles is "close" to being $3$-colorable. More precisely, the fractional chromatic number $χ_f(\mathcal{A})$ of the arrangement graph is bounded from above by $χ_f(\mathcal{A}) \le 3+O(\frac{1}{n})$, where $n$ is the number of pseudocircles of $\mathcal{A}$. Furthermore, we construct an infinite family of $4$-edge-critical $4$-regular planar graphs which are fractionally $3$-colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Generalization of Self-Improving Algorithms

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$, and the $x_i$'s are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$, where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$, and $H_\mathrm{S}$ and $H_\mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$'s under the \emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$'s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$'s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$'s are well-behaved. After an $O(\mathrm{poly}(n))$-time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected running times for sorting and DT, respectively, where $α(\cdot)$ is the inverse Ackermann function.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Computational Complexity of the $α$-Ham-Sandwich Problem

The classic Ham-Sandwich theorem states that for any $d$ measurable sets in $\mathbb{R}^d$, there is a hyperplane that bisects them simultaneously. An extension by Bárány, Hubard, and Jerónimo [DCG 2008] states that if the sets are convex and \emph{well-separated}, then for any given $α_1, \dots, α_d \in [0, 1]$, there is a unique oriented hyperplane that cuts off a respective fraction $α_1, \dots, α_d$ from each set. Steiger and Zhao [DCG 2010] proved a discrete analogue of this theorem, which we call the \emph{$α$-Ham-Sandwich theorem}. They gave an algorithm to find the hyperplane in time $O(n (\log n)^{d-3})$, where $n$ is the total number of input points. The computational complexity of this search problem in high dimensions is open, quite unlike the complexity of the Ham-Sandwich problem, which is now known to be PPA-complete (Filos-Ratsikas and Goldberg [STOC 2019]). Recently, Fearley, Gordon, Mehta, and Savani [ICALP 2019] introduced a new sub-class of CLS (Continuous Local Search) called \emph{Unique End-of-Potential Line} (UEOPL). This class captures problems in CLS that have unique solutions. We show that for the $α$-Ham-Sandwich theorem, the search problem of finding the dividing hyperplane lies in UEOPL. This gives the first non-trivial containment of the problem in a complexity class and places it in the company of classic search problems such as finding the fixed point of a contraction map, the unique sink orientation problem and the $P$-matrix linear complementarity problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays

We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in $\mathbb{Z}^d$. The construction must be {\em consistent} (that is, satisfy the natural extension of the Euclidean axioms) while resembling them as much as possible. Previous work has shown asymptotically tight results in two dimensions with $Θ(\log N)$ error, where resemblance between segments is measured with the Hausdorff distance, and $N$ is the $L_1$ distance between the two points. This construction was considered tight because of a $Ω(\log N)$ lower bound that applies to any consistent construction in $\mathbb{Z}^2$. In this paper we observe that the lower bound does not directly extend to higher dimensions. We give an alternative argument showing that any consistent construction in $d$ dimensions must have $Ω(\log^{1/(d-1)} N)$ error. We tie the error of a consistent construction in high dimensions to the error of similar {\em weak} constructions in two dimensions (constructions for which some points need not satisfy all the axioms). This not only opens the possibility for having constructions with $o(\log N)$ error in high dimensions, but also opens up an interesting line of research in the tradeoff between the number of axiom violations and the error of the construction. In order to show our lower bound, we also consider a colored variation of the concept of discrepancy of a set of points that we find of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Average Complexity of the $k$-Level

Let ${\cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The \emph{$k$-level} of ${\cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${\cal L}$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(n\cdot (k+1)^{1/3})$. Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the \emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$-spheres on the sphere $\mathbb{S}^d$ which are orthogonal to a set of random points on $\mathbb{S}^d$. In this model, we prove that the expected complexity of the $k$-level is of order $Θ((k+1)^{d-1})$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain

We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of $n$ vertices and $h$ holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of points of the domain. This helps us transform the problem so that we can search through the candidates more efficiently. Our algorithm computes both the diameter and the radius in $\min \{\,O(n^ω), O(n^2 + nh \log h + χ^2)\,\}$ time, where $ω<2.373$ denotes the matrix multiplication exponent and $χ\in Ω(n)\cap O(n^2)$ is the number of edges of the graph of oriented distances. We also provide a faster algorithm for computing the diameter that runs in $O(n^2 \log n)$ time.

0 citations0 reviewsNo code linkedOpen access