Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Vector Algebra: Graphical Method01:10

Vector Algebra: Graphical Method

12.5K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
12.5K
Visual Agnosia01:12

Visual Agnosia

248
Visual agnosia is a condition characterized by the inability to recognize visually presented objects despite having normal vision. For instance, a person with visual agnosia can describe the shape and color of an object but cannot identify or name it. This impairment does not affect their visual field, acuity, color vision, brightness discrimination, language, or memory. An example of this condition in a social setting is someone at a dinner party asking for "that silver thing with a round...
248
Coordination Number and Geometry02:57

Coordination Number and Geometry

16.2K
For transition metal complexes, the coordination number determines the geometry around the central metal ion. Table 1 compares coordination numbers to molecular geometry. The most common structures of the complexes in coordination compounds are octahedral, tetrahedral, and square planar.
16.2K
Bewley Lattice Diagram01:12

Bewley Lattice Diagram

780
The Bewley lattice diagram, developed by L. V. Bewley, effectively organizes the reflections occurring during transmission-line transients. It visually represents how voltage waves propagate and reflect within a transmission line, making it easier to understand the complex interactions that occur.
780
Lattice Centering and Coordination Number02:33

Lattice Centering and Coordination Number

9.7K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
9.7K
Theorems of Pappus and Guldinus: Problem Solving01:12

Theorems of Pappus and Guldinus: Problem Solving

773
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
773

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Fabrication of Micro-Chain Mail by Simultaneous, Patterned Electrodeposition on a Plane and Multiple Cylinders.

Angewandte Chemie (International ed. in English)·2018
Same author

Depth potential function for folding pattern representation, registration and analysis.

Medical image analysis·2008
Same author

Magnetic self-assembly of three-dimensional surfaces from planar sheets.

Proceedings of the National Academy of Sciences of the United States of America·2005
Same author

Tuning and comparing spatial normalization methods.

Medical image analysis·2004
Same author

Dissections: self-assembled aggregates that spontaneously reconfigure their structures when their environment changes.

Journal of the American Chemical Society·2002
Same author

Using hierarchical self-assembly to form three-dimensional lattices of spheres.

Journal of the American Chemical Society·2002

Related Experiment Video

Updated: Jul 30, 2025

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
05:39

Generating Strictly Controlled Stimuli for Figure Recognition Experiments

Published on: March 18, 2019

5.3K

Combinatorial Properties and Recognition of Unit Square Visibility Graphs.

Katrin Casel1, Henning Fernau2, Alexander Grigoriev3

  • 1Institut für Informatik, Humboldt-Universität zu Berlin, Unter den Linden 6, 10099 Berlin, Germany.

Discrete & Computational Geometry
|May 14, 2023
PubMed
Summary

This study investigates visibility graphs of unit squares. The recognition problem for unit square visibility graphs is proven to be NP-hard, settling an open question in computational geometry.

Keywords:
Geometric graph classesGraph recognitionVisibility graphsVisibility layout

More Related Videos

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations
11:15

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

4.7K
Author Spotlight: Assessment of Visual Acuity in Central Vision Loss Through Motion-Based Peripheral Vision Testing
06:25

Author Spotlight: Assessment of Visual Acuity in Central Vision Loss Through Motion-Based Peripheral Vision Testing

Published on: February 23, 2024

647

Related Experiment Videos

Last Updated: Jul 30, 2025

Generating Strictly Controlled Stimuli for Figure Recognition Experiments
05:39

Generating Strictly Controlled Stimuli for Figure Recognition Experiments

Published on: March 18, 2019

5.3K
Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations
11:15

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

4.7K
Author Spotlight: Assessment of Visual Acuity in Central Vision Loss Through Motion-Based Peripheral Vision Testing
06:25

Author Spotlight: Assessment of Visual Acuity in Central Vision Loss Through Motion-Based Peripheral Vision Testing

Published on: February 23, 2024

647

Area of Science:

  • Computational Geometry
  • Graph Theory
  • Combinatorics

Background:

  • Unit square visibility graphs (USV) model axis-parallel visibility between unit squares.
  • Unit square grid visibility graphs (USGV) are a specific type of USV on integer grids, related to rectilinear graphs.

Purpose of the Study:

  • To extend combinatorial results for USGV.
  • To determine the computational complexity of recognizing USV and USGV.
  • To settle an open question regarding the NP-hardness of USV recognition.

Main Methods:

  • Extending combinatorial results for USGV.
  • Analyzing the weak case of USGV recognition for area minimization.
  • Proving the NP-hardness of the USV recognition problem.

Main Results:

  • The area minimization variant of USGV recognition is NP-hard (weak case).
  • The recognition problem for general unit square visibility graphs (USV) is NP-hard.
  • New combinatorial insights for USV are provided.

Conclusions:

  • The recognition of unit square visibility graphs is computationally complex (NP-hard).
  • The findings contribute to understanding the complexity of geometric visibility problems.