Related Experiment Video
Updated: May 7, 2026
05:39
Generating Strictly Controlled Stimuli for Figure Recognition Experiments
Published on: March 18, 2019
Extreme point and halving edge search in abstract order types
Oswin Aichholzer1, Tillmann Miltzow, Alexander Pilz
1Institute for Software Technology, Graz University of Technology, Austria.
Computational Geometry : Theory and Applications
|October 5, 2013
Summary
Computational geometry problems like finding halving lines and convex hull points can be solved in linear time using only the abstract orientation (chirotope) of point sets, not just coordinates.
Area of Science:
- Computational Geometry
- Discrete Geometry
- Combinatorial Geometry
Background:
- Many geometric algorithms rely on point coordinates, limiting abstract applications.
- Knuth posed the challenge of solving problems using only abstract orientation data (chirotope).
Purpose of the Study:
- To determine if fundamental computational geometry problems can be solved in linear time using only abstract order types (chirotopes).
- To extend linear-time algorithms beyond coordinate-based representations.
Main Methods:
- Developed algorithms utilizing the chirotope (orientation of point triples) as the sole input.
- Proved feasibility for Euclidean-realizable sets first.
- Extended the findings to abstract, non-realizable order types.
Main Results:
- Linear-time algorithms were established for finding halving lines through any given point.
- Linear-time algorithms were developed for identifying convex hull edge intersections with supporting lines.
Conclusions:
- Problems previously requiring coordinates can be solved abstractly in linear time using chirotopes.
- This work generalizes fundamental computational geometry algorithms to abstract settings.
Related Concept Videos
01:22Absolute and Local Extreme Values
The highest and lowest values of a function, relative to a reference axis, are known as extreme values. These include absolute maximum and absolute minimum values, which represent the highest and lowest points the function reaches across its entire domain. Within a restricted portion of the function, the highest and lowest values are referred to as local maximum and local minimum values, respectively.Periodic functions, such as sine and cosine, show extreme values at infinitely many points due...
01:27Slant Asymptotes
A function's behavior is often guided by asymptotic constraints, where one term dominates another, defining a limiting trend. In the given scenario, the mathematical pattern follows a rational function: a cubic term in the numerator is divided by a squared term in the denominator. This results in a function with distinct characteristics, including an oblique asymptote, critical points, and undefined regions.The function's validity is determined by the denominator, which must be nonzero. This...
01:21Critical Numbers and the Closed Interval Method
Understanding the maximum and minimum values of a function is essential for analyzing its overall behavior. These values, often referred to as extrema, provide insight into how a function behaves across its domain. In mathematical terms, extrema can be either local—representing peaks and valleys within a limited region—or absolute, indicating the highest or lowest points over an entire interval.A function’s extrema occur at critical numbers, which are values in the domain where the derivative...
01:20Midpoint Rule
Approximating areas under curved boundaries is a common problem in applied mathematics, particularly when an exact calculation is difficult or impractical. One effective numerical method for this purpose is the Midpoint Rule, which provides an estimate of the area under a curve by using rectangular approximations over a specified interval.Description of the Midpoint RuleThe Midpoint Rule begins by dividing the given interval into a number of equal subintervals. For each subinterval, the...
01:26Optimization Problems
Optimization problems often involve identifying maximum or minimum values under specific constraints. A well-known example is determining the longest horizontal pipe that can be moved around a right-angled corner, where a 3-meter-wide hallway meets a 2-meter-wide hallway. This scenario, common in architectural design and industrial transport, can be understood conceptually through geometric and trigonometric reasoning.To visualize the problem, consider the pipe as a straight line that touches...
01:19Routh-Hurwitz Criterion II
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first column of the Routh...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first column of the Routh...