NDLI: Extremal problems on triangle areas in two and three dimensions

Please wait, while we are loading the content...

Dynamic coresets

Tighter bounds for random projections of manifolds

The complexity of the outer face in arrangements of random segments

A (slightly) faster algorithm for klee's measure problem

I/o-efficient efficient algorithms for computing contours on a terrain

Exact geometric-topological analysis of algebraic surfaces

On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism

Arrangements of geodesic arcs on the sphere

Towards persistence-based reconstruction in euclidean spaces

Locally uniform anisotropic meshing

A simple and efficient kinetic spanner

Fast enumeration algorithms for non-crossing geometric graphs

Consistent digital rays

Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications

Optimizing active ranges for consistent dynamic map labeling

Markov convexity and local rigidity of distorted metrics

On s-intersecting curves and related problems

Walking your dog in the woods in polynomial time

External memory planar point location with logarithmic updates

Predicates for line transversals to lines and line segments in three-dimensional space

New existence proofs ε-nets

Delpsc: a delaunay mesher for piecewise smooth complexes

Reeb spaces of piecewise linear mappings

Discrete laplace operator on meshed surfaces

Schnyder woods for higher genus triangulated surfaces

Polychromatic colorings of plane graphs

Combinatorial genericity and minimal rigidity

Geometry is everywhere, part XLVII: metrics, nets, dimensions, and measures

Maximum thick paths in static and dynamic environments

Diameters, centers, and approximating trees of delta-hyperbolicgeodesic spaces and graphs

On levels in arrangements of curves, iii: further improvements

Hinged dissections exist

Self-improving algorithms for delaunay triangulations

Robust construction of the three-dimensional flow complex

Extremal problems on triangle areas in two and three dimensions

On the computation of 3d periodic triangulations

Testing contractibility in planar rips complexes

Untangling triangulations through local explorations

Embedding and similarity search for point sets under translation

Coloring $k_{k}-free$ intersection graphs of geometric objects in the plane

Improved upper bounds on the crossing number

Circular partitions with applications to visualization and embeddings

Helly-type theorems for approximate covering

Markov incremental constructions

Visualizing and exploring planar algebraic arrangements: a web application

Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space

Delaunay triangulations of imprecise pointsin linear time after preprocessing

Intersecting convex sets by rays

Analyzing rigidity with pebble games

Minkowski sums of rotating convex polyhedra

Routing a maximum number of disks through a scene of moving obstacles

Extremal problems on triangle areas in two and three dimensions

Content Provider	ACM Digital Library
Author	Dumitrescu, Adrian Sharir, Micha Tóth, Csaba D.
Abstract	The study of extremal problems on triangle areas was initiated in a series of papers by Erdös and Purdy in the early 1970s. Here we present new results on such problems, concerning the number of triangles of the same area that are spanned by finite point sets in the plane and in 3-space, and the number of distinct areas determined by the triangles. In the plane, our main result is an $O(n^{44/19})$ = $O(n^{2.3158})$ upper bound on the number of unit-area triangles spanned by n points, which is the first improvement of the classical bound of $O(n^{7/3})$ from 1992. We also make progress in a number of important special cases: We show: (i) For points in convex position, there exist n-element point sets that span Ω(n log n) triangles of unit area. (ii) The number of triangles of minimum (nonzero) area determined by n points is at most $2/3(n^{2}$ -- n); there exist n-element point sets (for arbitrarily large n) that span $(6/π^{2}$ -- $o(1))n^{2}$ minimum-area triangles. (iii) The number of acute triangles of minimum area determined by n points is O(n); this is asymptotically tight. (iv) For n points in convex position, the number of triangles of minimum area is O(n); this is asymptotically tight. (v) If no three points are allowed to be collinear, there are n-element point sets that span (n log n) minimum-area triangles (in contrast to (ii), where collinearities are allowed and a quadratic lower bound holds). In 3-space we prove an $O(n^{17/7}β(n))$ = $O(n^{2.4286})$ upper bound on the number of unit-area triangles spanned by n points, where β(n) is an extremely slowly growing function related to the inverse Ackermann function. The best previous bound, $O(n^{8/3}),$ is another classical result of Erdös and Purdy from 1971. We further show, for point sets in3-space: (i) The number of minimum nonzero area triangles is at most $n^{2}$ + O(n), and this is worst-case optimal, up to a constant factor. (ii) There are n-element point sets that span $(n^{4/3})$ triangles of maximum area, all incident to a common point. In any n-element point set, the maximum number of maximum-area triangles incident to a common point is $O(n^{4/3+ε}),$ for any ε > 0. (iii) Every set of n points, not all on a line, determines at least $(n^{2/3}/β(n))$ triangles of distinct areas, which share a common side.
Starting Page	208
Ending Page	217
Page Count	10
File Format	PDF
ISBN	9781605580715
DOI	10.1145/1377676.1377709
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Discrete geometry Extremal combinatorics Unit triangle areas Maximum triangle areas Minimum triangle areas Point configurations Distinct triangle areas
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in