Fat Triangles Determine Linearly Many Holes
SIAM Journal on ComputingPublished 1 February 1994Open access
Matousek Jiri, János Pach, Micha Sharir, S. Sifrony, Emo Welzl
Citations160
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The authors show that for every fixed $\delta>0$ the following holds: if $F$ is a union of triangles, all of whose angles are at least $delta$, then the complement of F has $O(n)$ connected components and the boundary of F consists of straight segments.
Abstract
DCG
Keywords
Computer ScienceEngineering
Computational Geometry
3,606 Citations1985Franco P. Preparata, Michael Ian Shamos
This book clearly demonstrates that computational geometry in the plane is now a fairly well-understood branch of computer science and mathematics and points the way to the solution of the more challenging problems in dimensions higher than two.
Discrete & Computational GeometryOn the union of Jordan regions and collision-free translational motion amidst polygonal obstacles
375 Citations1986Klara Kedem, Ron Livné +2 more
An upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets is obtained and can be applied to planning a collision-free translational motion of a convex polygonB amidst several polygonal obstacles.
Journal of the ACMAn optimal algorithm for intersecting line segments in the plane
327 Citations1992Bernard Chazelle, Herbert Edelsbrunner
The authors present the first optimal algorithm for the following problem: given n line segments in the plane, compute all k pairwise intersections in O(n log n+k) time.
Journal of Combinatorial Theory Series ASharp upper and lower bounds on the length of general Davenport-Schinzel sequences
162 Citations1989Pankaj Agarwal, Micha Sharir +1 more
Sharp upper and lower bounds are obtained on the maximal length λs(n) of (n, s)-Davenport-Schinzel sequences, i.e., sequences composed of n symbols, having no two adjacent equal elements and containing no alternating subsequence of length s + 2.
Discrete & Computational GeometryPlanar realizations of nonlinear davenport-schinzel sequences by segments
135 Citations1988Ady Wiernik, Micha Sharir
Discrete & Computational GeometryOn the general motion-planning problem with two degrees of freedom
114 Citations1989Leonidas Guibas, Micha Sharir +1 more
Discrete & Computational GeometryThe complexity and construction of many faces in arrangements of lines and of segments
98 Citations1990Herbert Edelsbrunner, Leonidas Guibas +1 more
The proof takes an algorithmic approach, that is, an algorithm is described for the calculation of thesem faces and the upper bound for the total number of edges is derived from the analysis of the algorithm.
On K-Sets in Arrangements of Curves and Surfaces
95 Citations2018Micha Sharir
Lecture notes in computer scienceArrangements of curves in the plane — topology, combinatorics, and algorithms
93 Citations1988Herbert Edelsbrunner, Leonidas Guibas +4 more
A generalization of the zone theorem of [EOS], [CGL] to arrangements of curves, and an application of (some weaker variant of) that theorem to obtain a nearly quadratic incremental algorithm for the construction of such arrangements.
Reporting and Counting Intersections Between Two Sets of Line Segments
86 Citations1988Harry G. Mairson, Jorge Stolfi
This work considers the problem of computing all intersections between two sets S and T of line segments in the plane, where no two segments in S (similarly, T) intersect and presents an asymptotically optimal algorithm which reports all those intersections in O(n log n + k) time and O( n) space.
Computational GeometryEfficient hidden surface removal for objects with small union size
80 Citations1992Matthew J. Katz, Mark H. Overmars +1 more
Discrete & Computational GeometryOnk-sets in arrangements of curves and surfaces
60 Citations1991Micha Sharir
Borders that relate the maximum size of the (≤k)-set to the maximum sizes of a 0-set of a sample of the curves are obtained and various applications of these results are presented to arrangements of segments and curves, high-order Voronoi diagrams, partial stabbing of disjoint convex sets in the plane, and more.
Computational GeometryOn the union of fat wedges and separating a collection of segments by a line
59 Citations1993Alon Efrat, Günter Rote +1 more
This paper presents an O(n log n)-time algorithm for finding a separator line for a set of n segments, provided the ratio between the diameter of the set of segments and the length of the smallest segment is bounded.
Lecture notes in computer scienceA fast algorithm for polygon containment by translation
49 Citations1985Steven Fortune
The polygon containment problem is the problem of deciding whether one polygon, C, can be translated to fit within another polygon N, and an algorithm is presented that runs in time O (cn log cn) to solve this problem, in the case that the polygon C is convex.
Computer Vision Graphics and Image ProcessingNew algorithms for special cases of the hidden line elimination problem
48 Citations1987Ralf Hartmut Güting, Thomas Ottmann
Three special cases of increasing difficulty and generality of the hidden line elimination problem are studied, and applying some methods from computational geometry these problems can be solved with better worst-case bounds than those of the best known algorithms for the general problem.
ACM Transactions on GraphicsA simple output-sensitive algorithm for hidden surface removal
46 Citations1992Micha Sharir, Mark H. Overmars
A simple output-sensitive algorithm for hidden surface removal in a collection of nTriangles in space for which a (partial) depth order is known is derived.
Information and ComputationOptimal computation of finitely oriented convex hulls
32 Citations1987Gregory J. E. Rawlins, Derick Wood
Four versions of the “convex hull” of a simple finitely oriented polygon are defined and optimal algorithms to find them are given and it is shown that testing whether an arbitrary simple polygon is (finitely oriented) convex has worst-case time and space complexity θ ( n + f ) and η ( n ), respectively.
On arrangements of Jordan arcs with three intersections per pair
22 Citations1988Herbert Edelsbrunner, Leonidas Guibas +3 more
It is proved that the total number of subarcs that appear on the boundary of the union of n regions bounded by Jordan curves in the plane is only &THgr;(nα(n), where α(n) is the extremely slowly growing functional inverse of Ackermann's function.
Discrete & Computational GeometryOn arrangements of Jordan arcs with three intersections per pair
18 Citations1989Herbert Edelsbrunner, Leonidas Guibas +6 more
Information Processing LettersThe intersection searching problem for c-oriented polygons
11 Citations1991Xuehou Tan, Tomio Hirata +1 more
It is shown that a c- oriented polygon intersection query can be answered in O(log n+t) time using O(n log n) space, where n is the number of c-oriented polygons, each with a bounded number of edges, and t is thenumber of reported polygons.