Computational Geometry: Young Researchers Forum

Following previous years, one of the events that will take place during CG Week 2015 will be the Computational Geometry: Young Researchers Forum (CG:YRF), which is aimed at current and recent students. The active involvement by students and recent graduates in research, discussions, and social events has been a longstanding tradition in the CG community. Participation in a top-level event such as CG Week can be educating, motivating, and useful for networking, both with other students and with more senior scientists. The CG:YRF presents young researchers an opportunity to present their work (in progress as well as finished results) to the CG community in a friendly, open setting. Presentations will be given in the form of talks. A screening process (but no formal review) will ensure appropriate quality control.


Accepted Papers


  • Ramsay Dyer, Gert Vegter and Mathijs Wintraecken.
         Barycentric coordinate neighbourhoods in Riemannian manifolds [+]
    We quantify conditions that ensure that a signed measure on a Riemannian manifold has a well defined centre of mass. We then use this result to quantify the extent of a neighbourhood on which the Riemannian barycentric coordinates of a set of $n+1$ points on an $n$-manifold provide a true coordinate chart, i.e., the barycentric coordinates provide a diffeomorphism between a neighbourhood of a Euclidean simplex, and a neighbourhood containing the points on the manifold.
  • Jean-Daniel Boissonnat, David Cohen-Steiner and Alba Chiara De Vitis.
         Spectral Properties of Distance Matrices of High Dimensional
          Mixtures
    [+]
    We use spectral analysis of the distance matrices of high dimensional mixtures to learn a mixture of distributions. Our approach focuses on high-dimensional mixtures and uses concentration of measure. It applies to any distribution with concentration properties.
  • Supanut Chaidee and Kokichi Sugihara.
         Recognition of the Spherical Laguerre Voronoi Diagram [+]
    We construct an algorithm for judging whether or not a given tessellation on a sphere is a spherical Laguerre Voronoi diagram. This algorithm is based on the properties of polyhedra corresponding to the spherical Laguerre Voronoi diagram and their transformation in projective spaces.
  • Vissarion Fisikopoulos, Frank Staals and Constantinos Tsirogiannis.
         Computing the Expected Area of an Induced Triangle [+]
    Consider the following problem: given a set $P$ of $n$ points in the plane, compute the expected area of a triangle induced by $P$, that is, a triangle whose vertices are selected uniformly at random from the points in $P$. This problem is a special case of computing the expected area of the convex hull of $k$ points, selected uniformly at random from $P$. These problems are important in computing the functional diversity in Ecology. We present a simple exact algorithm for the problem that computes the expected triangle area in $O(n^2\log n)$ time, and extends to the case of computing the area of the convex hull of a size $k$ subset. Additionally, we present a $(1\pm\epsilon)$-approximation algorithm for the case in which the ratio $\rho$ between the furthest pair distance and the closest pair distance of the points in $P$ is bounded. With high probability (whp.) our algorithm computes an answer in the range $[(1-\epsilon)A^*,(1+\epsilon)A]$, where $A$ is the true expected triangle area, in $O(\frac{1}{\epsilon^{8/3}}\rho^4n^{5/3}\log^{4/3}n)$ expected time.
  • Mahmoodreza Jahanseir and Donald Sheehy.
         Transforming Hierarchical Trees on Metric Spaces [+]
    We show how a simple metric hierarchical tree called a cover tree transforms into a more complex one called a net-tree in linear time. We also propose two linear time algorithms to make a trade-off between depth and the degree of nodes in cover trees.
  • Saladi Rahul.
         Approximate Range Counting Revisited [+]
    This work presents several new results on approximate range counting. For a given query, if the actual count is $k$, then the data structures in this paper output a value, $\tau$, lying in the range $[(1-\vare)k,(1+\vare)k]$. The key results are the following: [A] A new technique for efficiently solving any approximate range counting problem is presented. This technique can be viewed as an enhancement of Aronov and Har-Peled's technique [{\it SIAM Journal of Computing, 2008}]; key reasons being the following: (1) The new technique is sensitive to the value of $k$: As an application, this work presents a structure for approximate halfspace range counting in $\IR^d, d\geq 4$ which occupies $O(n)$ space and solves the query in $O((n/k)^{1-1/\lfloor d/2\rfloor})$ time. When $k=\Theta(n)$, then the query time is $O(1)$. (2) The new technique handles colored range searching problems: As an application, the orthogonal colored range counting problem is solved. Existing structures for exact counting use $O(n^d)$ space to answer the query in $O(polylog n)$ query time. Improving these bounds substantially would require improving the best exponent of matrix multiplication. Therefore, if one is willing for an approximation, an attractive result is obtained: an $O(n polylog n)$ space data structure and an $O(polylog n)$ query time algorithm. [B] An optimal solution for approximate rectangle stabbing counting problems in $\IR^2$. This is achieved by a non-trivial reduction to planar point location. [C] Finally, an efficient solution is obtained for $3$-sided orthogonal colored range counting. The result is obtained by a non-trivial combination of two different types of random sampling techniques and a reduction to non-colored range searching problem.
  • Wei Zhan and Jian Li.
         Almost All Even Yao-Yao Graphs Are Spanners [+]
    In this abstract we show that, for any integer $k\geq 42$, the Yao-Yao graph $\YY{2k}$ is a $t_k$-spanner, with stretch factor $t_k=4.27+O(k^{-1})$ when $k$ tends to infinity. Our result generalizes the best known result which asserts that all $\YY{6k}$ are spanners for $k$ large enough [Bauer and Damian, SODA'13].
  • Udo Hoffmann.
         Computing the planar slope number [+]
    The planar slope number of a planar graph G is dened as the minimal number of slopes that is required for a straight line drawing of G. We show that determining the planar slope number is hard in the existential theory of the reals. We point out consequences for drawings that minimize the planar slope number.
  • Tyler Speaker Mayer, Gui Citovsky, Joseph Mitchell, Esther Arkin,
      Aritra Banik, Paz Carmi, Matthew Katz and Su Jia.
         Network Optimization on Partitioned Pairs of Points [+]
    Given a set $S = \bigcup_{i=1}^{n}\{p_i, q_i\}$ of $n$ pairs of points in a metric space, we study the problem of computing, what we call, a {\em feasible} partition $S = S_1 \cup S_2$ such that $p_i \in S_1$ if and only $q_i \in S_2 \: \forall \: i$. The partition should optimize the cost of a {\em pair} of networks, one built on $S_1$, and one built on $S_2$. In this work we consider the network structures to be matchings, minimum spanning trees (MSTs), traveling salesman tours (TSP tours), or their bottleneck equivalents. Let $f(X)$ be some network structure computed on point set $X$ and let $\lambda(f(X))$ be the bottleneck edge of that network. For each of the aforementioned network structures we consider the objective of (1) minimizing $|f(S_1)| + |f(S_2)|$, (2) minimizing $max\{|f(S_1)|,|f(S_2)|\}$, or (3) minimizing $max\{|\lambda(f(S_1))|, |\lambda(f(S_2))|\}$. Here, $|\cdot|$ denotes the sum of the edge lengths. We show several hardness results and an $O(1)$ approximation for every objective considered. Our results are summarized in Table \ref{results_table} and full details can be found in \cite{arkin2016Network}.
  • Jean Cardinal, John Iacono and Aurélien Ooms.
         A geometric approach to $k$-SUM [+]
    It is known that $k$-SUM can be solved using $\tilde{O}(n^{\lceil\frac{k}{2}\rceil})$ time and linear queries (here the notation $\tilde{O}$ ignores polylogarithmic factors). On the other hand, there is a point location algorithm due to Meiser that shows the existence of $\tilde{O}(n^4)$-depth algebraic computation trees for $k$-SUM. By streamlining Meiser's algorithm, we prove $k$-SUM can be solved using $\tilde{O}(n^3)$ expected linear queries in $\tilde{O}(n^{\lceil\frac{k}{2}\rceil+8})$ expected time. Thus, we show that it is possible to have an algorithm with a runtime almost identical (up to the +8) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of $k$. The new algorithms we present rely heavily on fundamental tools from computational geometry: $\varepsilon$-nets and cuttings. A preprint is available at \url{http://arxiv.org/abs/1512.06678}.
  • Clément Maria and Jonathan Spreer.
         Classification of Normal Curves on a Tetrahedron [+]
    In this article, we give a combinatorial classification of all normal curves drawn on the boundary of a tetrahedron. We characterise normal curves in terms of intersection numbers with the edges of the tetrahedron.
  • Federico Iuricich, Riccardo Fellegara and Leila De Floriani.
         Homology preserving simplification for top-based
          representations
    [+]
    Topological features provide global quantitative and qualitative information about a shape, such as the number of the connected components, and the number of holes and tunnels. These information are especially important in high-dimensional data analysis, where pure geometric tools are usually not sufficient. When dealing with simplicial homology, the size of simplicial complex is the major concern, since all the algorithms available in literature are mainly affected by the number of simplices of the complex. The classical approach for computing the homology of a simplicial complex is based on the Smith Normal Form (SNF) reduction applied to the boundary matrices describing the boundary maps. This method is theoretically valid in any dimension, but it has intrinsic limitations linked to the size of matrices and to the high complexity of reduction algorithms. Other methods have been proposed for improving the performances of SNF reduction, but the only scalable approach still remains the simplification of the original complex in order to reduce its size without changing its homology. Edge contraction is from a long time a tool of choice for simplifying simplicial complexes. It has been used in computer graphics and visualization and more recently in topological data analysis for reducing the size of higher dimensional simplicial complexes. Edge contraction on its own does not preserve the homological information but a check, called link condition, has been developed for verifying whether the contraction of an edge preserves homology or not. In our work, we consider the efficient definition of a simplification algorithm, that combines an efficient top-based representation for a simplicial complex with an edge contraction simplification procedure. Our contribution is: (i) the definition of a dimension-independent edge contraction and of a link condition for top-based representations; (ii) the implementation of an efficient algorithm for computing and simplifying a d-simplicial complex on a specific top-based representation, the Stellar tree and (iii) an experimental comparison with respect to the state-of-the-art data structure for performing edge contractions, the Skeleton Blockers.
  • Sara Scaramuccia, Federico Iuricich, Claudia Landi and Leila De Floriani.
         Towards the Analysis of Multivariate Data based on Discrete Morse
          Theory
    [+]
    We propose a new algorithm for computing a Forman gradient on a CW-complex on which a vector-valued function is defined. We prove that our algorithm is equivalent to the state-of-the-art algorithms, i.e., it retrieves a Forman gradient compatible with the multidimensional persistent homology induced by the vector-valued function, being at the same time faster and more compact.
  • Aruni Choudhary, Michael Kerber and Sharath Raghvendra.
         Local Structures for Approximating Rips Filtrations [+]
    (Vietoris-)Rips filtrations are important structures used to infer topological properties of metric spaces. Unfortunately, they pose a significant computational challenge, particularly when the data has high dimension. We present a new technique to $O(\sqrt{d})$-approximate the topological information carried by the Rips filtration, with at most $n2^{O(d\log d)}$ $d$-simplices per scale in the filtration.
  • Su Jia, Jie Gao and Joseph Mitchell.
         Exact and Approximation Algorithms for Time-Window TSP [+]
    We study a version of the time-window traveling salesman problem (TWTSP): given a speed bound B for a robot, a set of cities each having a time window during which it must be visited, and a shortest path for the robot to visit all cities within their respective time windows, if possible to do so.
  • Kirk Gardner, Nicholas Cavanna and Don Sheehy.
         Generalized Coverage in Homological Sensor Networks [+]
    In their seminal work on homological sensor networks, de Silva and Ghrist showed the surprising fact that it?s possible to certify the coverage of a coordinate-free sensor network even with very minimal knowledge of the space to be covered [2]. We give a new, simpler proof of the de Silva-Ghrist Topological Coverage Criterion (TCC) that eliminates any assumptions about the smoothness of the boundary of the underlying space, allowing the results to be applied to much more general problems. The new proof factors the geometric, topological, and combinatorial aspects of this approach. This allows us to extend the TCC to support k-coverage, in which the domain is covered by k sensors, and weighted coverage, in which sensors have varying sensing radii.
  • Sándor Fekete, Qian Li, Joseph Mitchell and Christian Scheffer.
         Universal Guards: Guarding All Polygonalizations of a Point Set in
          the Plane
    [+]
    The Art Gallery Problem (AGP) seeks to find the fewest guards to see all of a given domain; in its classic combinatorial variant (posed by Victor Klee), it asks for the number of guards that always suffice and are sometimes necessary to guard any simple $n$-gon: the answer is the well known $\lfloor n/3\rfloor$. While Klee's question was posed about guarding an $n$-vertex {\em simple polygon}, a related question about {\em point sets} was posed at the 2014 Goodman-Pollack Fest (NYU, November 2014): Given a set $S$ of $n$ points in the plane, how many guards always suffice to guard any simple polygon with vertex set $S$? A set of guards that guard every polygonalization of $S$ is said to be a set of {\em universal guards} for the point set. The question is how many universal guards are always sufficient, and sometimes necessary, for any set of $n$ points? We give the first set of results on universal guarding. We focus here on the case in which guards must be placed at a subset (the {\em guarded points}) of the input set $S$ and thus will be vertex guards for any polygonalization of~$S$.
  • Nicholas Cavanna, Kirk Gardner and Donald Sheehy.
         Certified Homology Inference [+]
    The goal of homology inference is to compute the shape of a space from a finite point set sampled near it. Given such a sample, one may want to know when we can reliably infer the homology of the space in question. Naturally, this requires making assumptions on the sample as well as the underlying space. Niyogi, Smale, and Weinberger showed that one can infer the homology of a smooth manifold from finite points chosen uniformly at random. Chazal and Lieutier relaxed this to include non-smooth bounded spaces in R^d via the so-called weak feature size. Both assume good samples in the sense that there must be a sampled point within ? of every point in the space. Vin de Silva and Robert Ghrist showed how to certify if a point set contains a good sample of a shrunken version of a space assuming one can compute the distance from a point to the boundary. We show when and how these approaches can be combined in order to provide a computable inference of the homology of the domain. We do so on more general spaces in R^d, only assuming a lower bound on the weak feature size of a compact, locally contractible domain, and that we can compute the distance to the boundary.
  • Ahmed Abdelrazek.
         Homology Localization by Hierarchical Blowups [+]
    Topological descriptors such as the generators of homology groups are very useful in the analysis of complex data sets. It is often desired to find the smallest such generators to help localize the interesting features. One interpretation of localization utilizes a covering of the underlying space and computes generators contained within these covers. A similar construction was later used to compute persistence homology for smaller subsets in parallel before gluing the results. In this presentation, we describe a more efficient version of this construction and discuss how it can be used to find generators within a large class of subspaces.
  • Gill Barequet and Mira Shalah.
         Improved Bounds on the Growth Constant of Polyiamonds [+]
    In this paper we provide improved lower and upper bounds on the asymptotic growth constant of polyiamonds, proving that it is between~2.8424 and~3.6050.
  • Arijit Bishnu, Sameer Desai and Arijit Ghosh.
         New results on gap ratio and correlation with other uniformity
          measures
    [+]
    Gap ratio is a uniformity measure that is a ratio of covering radius and the packing radius. Following up on previous work, we show a constructive lower bound for gap ratio in the unit square using furthest point algorithm. We do exhaustive experiments to establish high correlation between gap ratio and other measures of uniformity like star discrepancy, point-to-point distance measure and volumetric measures. Wherever possible we also give theoretical results in support of the high correlation.
  • Timothy Chan and Dimitrios Skrepetos.
         All-Pairs Shortest Paths in Unit Disk Graphs in Slightly Subquadratic
          Time
    [+]
    In this paper we study the all-pairs shortest paths problem in (unweighted) unit disk graphs. The previous best solution for this problem required $O(n^2\log n)$ time, by running the $O(n\log{n})$-time single-source shortest path algorithm of Cabello and Jej?i? (2015) from every source vertex, where $n$ is the number of vertices. We not only manage to eliminate the logarithmic factor, but also obtain the first (slightly) subquadratic algorithm for the problem, running in $O(n^{2}\sqrt{\frac{\log{\log{n}}}{\log{n}}})$ time. Our algorithm computes an implicit representation of all the shortest paths, and, in the same amount of time, can also compute the diameter of the graph.
  • Brittany Fasy, Selcuk Karakoc and Carola Wenk.
         On Minimum Area Homotopies [+]
    In this work, we will define the minimum homotopy area for closed curves and we will give a method to calculate it. The minimum homotopy area between two simple curves are defined by E. Chambers and Y. Wang, and they gave an algorithm to compute it. This work is a generalization of theirs. Our method will be first calculating it for a class of curves, namely self-overlapping curves and then breaking a general curve into self-overlapping sub-curves. We will also give some properties of a minimum homotopy, one that minimizes the area.


CG:YRF Chair

Erin Wolf Chambers, Saint Louis University, USA, echambe5 @ slu.edu

CG:YRF Program Committee

Therese Biedl, University of Waterloo
Erin Chambers, Saint Louis University (chair)
Vin de Silva, Pomona College
Vida Dujmovińá, University of Ottawa
Jeff Phillips, University of Utah
Donald Sheehy, University of Connecticut
Mikael Vejdemo-Johansson, Stockholm, Sweden
Carola Wenk, Tulane University

Submission Guidelines

  • The idea of the event is for young researchers to present new and ongoing work. Therefore, the work should not have appeared in print in a formally reviewed proceedings volume or journal by the time of submission.
  • Topics must fit into the general context of SoCG, as described in the call for SoCG submissions.
  • At least one of the authors must be a young researcher; defined as not having received a formal doctorate before 2014, who will present the work during CG:YRF.
  • A submission must be in the form of a 2-page abstract, formatted according to this style file and submitted via easychair.
  • Accepted abstracts will be compiled in a booklet of abstracts that will be distributed among the participants; this should not be considered a formal publication. In particular, participants are encouraged to submit (an extended version of) their presented work to a conference with formal proceedings and/or to a journal.

We will employ a two-phase screening process. After the first review phase, there will be a notification of either rejection (if the result is clearly out of context, or technically incorrect), or conditional acceptance, accompanied with a description of required changes to be made (either with respect to content or format). In the second phase, we will check whether the changes have been implemented satisfactorily. The screening process is intended to ensure the technical quality of the presented work. Submissions that are not well written risk rejection, irrespective of correctness. Authors are requested to have their submissions proofread by their advisor or another experienced scientist.

Important Dates

(deadlines are 23:59 Honolulu time)

March 28, 2016: Deadline for submissions
Apr 1, 2016: Applications for student/postdoc support due
April 22, 2016: Notification of conditional acceptance
April 29, 2016: Deadline for revisions
May 6, 2016: Notification of acceptance
Jun 14-18, 2016: CG-Week 2016