An official website of the United States government
Given a set of points P and axis-aligned rectangles R in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k2) rectangles, we can expose at least Ω(1/k) of the optimal number of points.
more »
« less
Examining and developing fourth grade children’s area estimation performance
Abstract This study explored children’s area estimation performance. Two groups of fourth grade children completed area estimation tasks with rectangles ranging from 5 to 200 square units. A randomly assigned treatment group completed instructional sessions that involved a conceptual area measurement strategy along with numerical feedback. Children tended to underestimate areas of rectangles. Furthermore, rectangle size was related to performance such that estimation error and variability increased as rectangle size increased. The treatment group exhibited significantly improved area estimation performance in terms of accuracy, as well as reduced variability and instances of extreme responses. Area measurement estimation findings are related to a Hypothetical Learning Trajectory for area measurement.
more »
« less
- Award ID(s):
- 1222944
- PAR ID:
- 10459624
- Publisher / Repository:
- Wiley-Blackwell
- Date Published:
- Journal Name:
- School Science and Mathematics
- Volume:
- 120
- Issue:
- 2
- ISSN:
- 0036-6803
- Page Range / eLocation ID:
- p. 67-78
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Magic squares have been extremely useful and popular in combinatorics and statistics. One generalization of magic squares ismagic rectangleswhich are useful for designing experiments in statistics. A necessary and sufficient condition for the existence of magic rectangles restricts the number of rows and columns to be either both odd or both even. In this paper, we generalize magic rectangles to even by oddnearly magic rectangles. We also prove necessary and sufficient conditions for the existence of a nearly magic rectangle, and construct one for each parameter set for which they exist.more » « less
-
In this paper we study two geometric data structure problems in the special case when input objects or queries are fat rectangles. We show that in this case a significant improvement compared to the general case can be achieved. We describe data structures that answer two- and three-dimensional orthogonal range reporting queries in the case when the query range is a fat rectangle. Our two-dimensional data structure uses O(n) words and supports queries in O(loglog U + k) time, where n is the number of points in the data structure, U is the size of the universe and k is the number of points in the query range. Our three-dimensional data structure needs O(n log^ε U) words of space and answers queries in O(loglog U + k) time. We also consider the rectangle stabbing problem on a set of three-dimensional fat rectangles. Our data structure uses O(n) space and answers stabbing queries in O(log U loglog U + k) time.more » « less
-
Abstract The $$p$$-Laplacian has attracted more and more attention in data analysis disciplines in the past decade. However, there is still a knowledge gap about its behavior, which limits its practical application. In this paper, we are interested in its iterative behavior in domains contained in two-dimensional Euclidean space. Given a connected set $$\varOmega _0 \subset \mathbb{R}^2$$, define a sequence of sets $$(\varOmega _n)_{n=0}^{\infty }$$ where $$\varOmega _{n+1}$$ is the subset of $$\varOmega _n$$ where the first eigenfunction of the (properly normalized) Neumann $$p$$-Laplacian $$ -\varDelta ^{(p)} \phi = \lambda _1 |\phi |^{p-2} \phi $$ is positive (or negative). For $p=1$, this is also referred to as the ratio cut of the domain. We conjecture that these sets converge to the set of rectangles with eccentricity bounded by 2 in the Gromov–Hausdorff distance as long as they have a certain distance to the boundary $$\partial \varOmega _0$$. We establish some aspects of this conjecture for $p=1$ where we prove that (1) the 1-Laplacian spectral cut of domains sufficiently close to rectangles is a circular arc that is closer to flat than the original domain (leading eventually to quadrilaterals) and (2) quadrilaterals close to a rectangle of aspect ratio $$2$$ stay close to quadrilaterals and move closer to rectangles in a suitable metric. We also discuss some numerical aspects and pose many open questions.more » « less
-
BackgroundWhen unaddressed, contamination in child maltreatment research, in which some proportion of children recruited for a nonmaltreated comparison group are exposed to maltreatment, downwardly biases the significance and magnitude of effect size estimates. This study extends previous contamination research by investigating how a dual‐measurement strategy of detecting and controlling contamination impacts causal effect size estimates of child behavior problems. MethodsThis study included 634 children from the LONGSCAN study with 63 cases of confirmed child maltreatment after age 8 and 571 cases without confirmed child maltreatment. Confirmed child maltreatment and internalizing and externalizing behaviors were recorded every 2 years between ages 4 and 16. Contamination in the nonmaltreated comparison group was identified and controlled by either a prospective self‐report assessment at ages 12, 14, and 16 or by a one‐time retrospective self‐report assessment at age 18. Synthetic control methods were used to establish causal effects and quantify the impact of contamination when it was not controlled, when it was controlled for by prospective self‐reports, and when it was controlled for by retrospective self‐reports. ResultsRates of contamination ranged from 62% to 67%. Without controlling for contamination, causal effect size estimates for internalizing behaviors were not statistically significant. Causal effects only became statistically significant after controlling contamination identified from either prospective or retrospective reports and effect sizes increased by between 17% and 54%. Controlling contamination had a smaller impact on effect size increases for externalizing behaviors but did produce a statistically significant overall effect, relative to the model ignoring contamination, when prospective methods were used. ConclusionsThe presence of contamination in a nonmaltreated comparison group can underestimate the magnitude and statistical significance of causal effect size estimates, especially when investigating internalizing behavior problems. Addressing contamination can facilitate the replication of results across studies.more » « less
