| 1. |
- Arkin, Esther M, et al.
(author)
-
Convex transversals
- 2014
-
In: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 47:2, s. 224-239
-
Journal article (peer-reviewed)abstract
- We answer the question initially posed by Arik Tamir at the Fourth NYU Computational Geometry Day (March, 1987): “Given a collection of compact sets, can one decide in polynomial time whether there exists a convex body whose boundary intersects every set in the collection?”We prove that when the sets are segments in the plane, deciding existence of the convex stabber is NP-hard. The problem remains NP-hard if the sets are regular polygons. We also show that in 3D the stabbing problem is hard when the sets are balls. On the positive side, we give a polynomial-time algorithm to find a convex transversal of a maximum number of pairwise-disjoint segments in 2D if the vertices of the transversal are restricted to a given set of points. Our algorithm also finds a convex stabber of the maximum number of a set of convex pseudodisks in the plane.The stabbing problem is related to “convexity” of point sets measured as the minimum distance by which the points must be shifted in order to arrive in convex position; we give a PTAS to find the minimum shift in 2D, and a 2-approximation in any dimension. We also consider stabbing with vertices of a regular polygon – a problem closely related to approximate symmetry detection.
|
|
| 2. |
- Arkin, Esther M, et al.
(author)
-
Shortest path to a segment and quickest visibility queries
- 2016
-
In: LIPIcs-Leibniz International Proceedings in Informatics. ; , s. 77-100
-
Conference paper (peer-reviewed)abstract
- We show how to preprocess a polygonal domain with a xed starting point s in order to answer eciently the following queries: Given a point q, how should one move from s in order to see q as soon as possible? This query resembles the well-known shortestpath- to-a-point query, except that the latter asks for the fastest way to reach q, instead of seeing it. Our solution methods include a data structure for a di erent generalization of shortest-path-to-a-point queries, which may be of independent interest: to report eciently a shortest path from s to a query segment in the domain.
|
|
| 3. |
- Ebbers-Baumann, Annette, et al.
(author)
-
Embedding point sets into plane graphs of small dilation
- 2007
-
In: International Journal of Computational Geometry and Applications. - 0218-1959. ; 17:3, s. 201-230
-
Journal article (peer-reviewed)abstract
- Let S be a set of points in the plane. What is the minimum possible dilation of all plane graphs that contain S? Even for a set S as simple as five points evenly placed on the circle, this question seems hard to answer; it is not even clear if there exists a lower bound > 1. In this paper we provide the first upper and lower bounds for the embedding problem. 1. Each finite point set can be embedded in to the vertex set of a finite triangulation of dilation <= 1.1247. 2. Each embedding of a closed convex curve has dilation >= 1.00157. 3. Let P be the plane graph that results from intersecting n infinite families of equidistant, parallel lines in general position. Then the vertex set of P has dilation >= 2/root 3 approximate to 1.1547.
|
|
| 4. |
- Walker, Anthony P., et al.
(author)
-
Integrating the evidence for a terrestrial carbon sink caused by increasing atmospheric CO2
- 2021
-
In: New Phytologist. - : John Wiley & Sons. - 0028-646X .- 1469-8137. ; 229:5, s. 2413-2445
-
Journal article (peer-reviewed)abstract
- Atmospheric carbon dioxide concentration ([CO2]) is increasing, which increases leaf‐scale photosynthesis and intrinsic water‐use efficiency. These direct responses have the potential to increase plant growth, vegetation biomass, and soil organic matter; transferring carbon from the atmosphere into terrestrial ecosystems (a carbon sink). A substantial global terrestrial carbon sink would slow the rate of [CO2] increase and thus climate change. However, ecosystem CO2 responses are complex or confounded by concurrent changes in multiple agents of global change and evidence for a [CO2]‐driven terrestrial carbon sink can appear contradictory. Here we synthesize theory and broad, multidisciplinary evidence for the effects of increasing [CO2] (iCO2) on the global terrestrial carbon sink. Evidence suggests a substantial increase in global photosynthesis since pre‐industrial times. Established theory, supported by experiments, indicates that iCO2 is likely responsible for about half of the increase. Global carbon budgeting, atmospheric data, and forest inventories indicate a historical carbon sink, and these apparent iCO2 responses are high in comparison to experiments and predictions from theory. Plant mortality and soil carbon iCO2 responses are highly uncertain. In conclusion, a range of evidence supports a positive terrestrial carbon sink in response to iCO2, albeit with uncertain magnitude and strong suggestion of a role for additional agents of global change.
|
|
